单调栈

  |  

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

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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