Home 单调栈
Post
Cancel

单调栈

单调栈是满足单调性的栈结构, 即实时维护栈内部的元素满足某种单调性.

将一个元素插入单调栈时,为了维护栈的单调性,需要在保证将该元素插入到栈顶后整个栈满足单调性的前提下弹出最少的元素。

P5788 【模板】单调栈

例题

题意: 输入 n 个数, 找到每个数在它后面输入的数中第一个比它大的数的下标.

思路: 栈要么为空, 要么满足里面的数是单调不增的. 每输入一个数, 就和栈顶元素比较, 如果比栈顶元素大, 说明当前下标就是栈顶元素的 f 值. 循环结束后如果栈不空, 说明栈顶元素大于当前元素, 那么比栈顶元素大的数就还没出现, 需要看后续的输入.

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
int n,a[3000010],f[3000010];
stack<int>st;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        while(!st.empty()&&a[st.top()]<a[i]){
            f[st.top()]=i;
            st.pop();
        }
        st.push(i);
    }
    for(int i=1;i<n;++i)
        printf("%d ",f[i]);
    printf("%d\n",f[n]);
    return 0;
}

P1901 发射站

Link

我们定义「左边」为下标 j, 满足: j<ih[j]>h[i], 「右边」为下标 k, 满足: i<kh[k]>h[i].

构造一个单调不增的栈. 栈中所有的元素要么没有左边, 要么已经找到了左边, 并且其左边也在栈中. 最重要的是, 栈中的所有元素都没有右边. 一旦找到了右边 (无论有无左边), 就一定会弹出该元素.

  • 如果栈顶元素高度大于当前元素高度, 说明栈顶元素就是当前元素的左边;
  • 如果栈顶元素高度小于当前元素高度, 说明当前元素就是栈顶元素的右边. 但是还没完, 要看看栈里面还有没有高度低于当前元素的元素, 即高度大于栈顶元素但是低于当前元素的元素. 如果有, 则当前元素也是这些元素的右边. 这些元素的右边找到后, 就可以从栈中取出来了. 将它们 (栈中所有高度小于当前元素的元素) 全部取出来后, 如果此时栈非空, 那么就需要判断当前元素的左边在不在栈中. 用另一个栈 temp 存储依次弹出来的、高度与当前元素相等的所有元素, 如果此时栈中还剩下元素, 那么栈顶元素的高度就一定大于当前元素, 也就是说此时的栈顶元素就是当前元素的右边. 即使没找到当前元素的右边也没关系, 但是别忘了把 temp 中的数据还原回去.
  • 如果栈顶元素高度等于当前元素高度, 那么就和上一步中相等部分的判断方式相同.

AC 代码:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
using namespace std;
int n,ans;
int h[1000010],v[1000010],w[1000010];
stack<int>st,temp;
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d%d",&h[i],&v[i]);
        if(!st.empty()){
            int top=st.top();
            if(h[top]>h[i]){
                w[top]+=v[i];
            }else if(h[top]<h[i]){
                while(!st.empty()&&h[st.top()]<h[i]){
                    w[i]+=v[st.top()];
                    st.pop();
                }
                if(!st.empty()){
                    while(!st.empty()&&h[st.top()]==h[i]){
                        temp.push(st.top());
                        st.pop();
                    }
                    if(!st.empty()){
                        w[st.top()]+=v[i];
                    }
                    while(!temp.empty()){
                        st.push(temp.top());
                        temp.pop();
                    }
                }
            }else{
                while(!st.empty()&&h[st.top()]==h[i]){
                    temp.push(st.top());
                    st.pop();
                }
                if(!st.empty()){
                    w[st.top()]+=v[i];
                }
                while(!temp.empty()){
                    st.push(temp.top());
                    temp.pop();
                }
            }
        }
        st.push(i);
    }
    for(int i=1;i<=n;++i)
        ans=max(ans,w[i]);
    printf("%d\n", ans);
    return 0;
}

力扣: 接雨水

Link

记得很久以前在力扣上写过一道经典的「单调栈」的题…就是这题.

查看提交记录, 上一次通过时还是 2020 年 6 月 26 日.

这次的写法, 执行用时和内存消耗都是上次的 4 倍 😱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int trap(vector<int>& height) {
        stack<int>st;
        int n=height.size(),ans=0;
        vector<int>num(n+1,1);
        for(int i=0;i<n;++i){
            if(!st.empty()&&height[st.top()]<height[i]){
                int temp=0,maxn=0;
                while(!st.empty()&&height[st.top()]<height[i]){
                    maxn=max(maxn,height[st.top()]);
                    num[i]+=num[st.top()];
                    ans+=num[st.top()]*(height[i]-height[st.top()]);
                    st.pop();
                }
                if(st.empty()){
                    ans-=(num[i]-1)*(height[i]-maxn);
                }
            }
            st.push(i);
        }
        return ans;
    }
};

好吧 的确是做复杂了. 贴个简单高效的代码吧.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> st;
        for (int i = 0; i < height.size(); i++)
        {
            while (!st.empty() && height[st.top()] < height[i])
            {
                int cur = st.top();
                st.pop();
                if (st.empty()) break;
                int l = st.top();
                int h = min(height[i], height[l]) - height[cur];
                ans += (i - l - 1) * h;
            }
            st.push(i);
        }
        return ans;
    }
};
This post is licensed under CC BY 4.0 by the author.