算法数据结构

单调栈：两侧距离最近的更大元素

字数统计: 897字   |   阅读时长: 3分
, , ,

摘要: 单调栈的算法原理，代码模板和应用

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们以力扣 84. 柱状图中最大的矩形 为模板题，串讲一下单调栈的思路和代码。在文章 单调栈题目汇总 中列出了单调栈的题目清单。

单调栈基本模型

单调栈的核心使用场景是摊销O(1)地获得所有位置上两侧第一个比它大/小的数的位置。

其基本的问题是给定数组 A[i], 求 L[i], R[i]：

1
2
L[i] := [0..i-1] 上离 i 最近的大于 A[i] 的下标
R[i] := [i+1..n-1] 上离 i 最近的大于 A[i] 的下标

一种便于理解的基本模型是直方图最大矩形，正是后面的模板题。

模板题：84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

示例 2：
输入： heights = [2,4]
输出： 4

提示：

1
2
1 <= heights.length <=1e5
0 <= heights[i] <= 1e4

算法1：单调栈

维护一个单调不减的栈，保存当前枚举元素 cur 左侧小于等于 cur 的元素的下标，其中栈顶离cur 最近，它是 cur 左侧第一个比它小的元素的位置。

枚举数组所有下标 j，把所有大于 nums[j] 的栈顶都弹出，直到栈顶小于等于 nums[j]，然后将 j 压入(所有下标都会压入)，当前枚举的 j 就处理完了。答案在出栈时更新，出栈元素为 cur：

1
2
cur = st.top();
st.pop();

此时对于已经弹出的 cur，当前的栈顶是 cur 左侧第一个小于等于 cur 的，nums[j] 是 cur 右侧第一个大于 cur 的。cur 对应的矩形宽度为：

1
w = j - st.top() - 1;

当栈顶有连续的几个值相等的下标时，最后一个弹出的 cur 会把左侧第一个小于 cur 的下标取到，先弹出的取到的不是左侧第一个小于 cur 的，只是第一个小于等于 cur的，这在此题不影响，但如果要返回每个位置能取到的最大矩形，则需要额外处理先弹出的几个下标。

栈底始终放一个 -1 处理 nums[j] 比栈里所有元素都小的情况。

每个元素都要进栈一次出栈一次，总时间复杂度 O(N)

代码 (C++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        if(heights.empty()) return 0;
        int n = heights.size();
        stack<int> st({-1});
        int result = 0;
        for(int i = 0; i < n; ++i)
        {
            if(st.top() == -1 || heights[st.top()] <= heights[i])
                st.push(i);
            else
            {
                while(st.top() != -1 && heights[st.top()] > heights[i])
                {
                    int index = st.top();
                    st.pop();
                    int w = i - st.top() - 1;
                    int area = w * heights[index];
                    result = max(result, area);
                }
                st.push(i);
            }
        }
        while(st.top() != -1)
        {
            int index = st.top();
            st.pop();
            int w = n - st.top() - 1;
            int area = w * heights[index];
            result = max(result, area);
        }
        return result;
    }
};

算法2：中心扩散法

参考文章 中心扩散法。

Share