22.单调栈

发表于 更新于 分类于 ，

单调栈

栈内元素保持单调递增或单调递减的顺序，常用于解决"寻找最近的比当前元素大/小的元素"这类问题。

设栈 \(S\) 中元素为 \(S_1, S_2, ..., S_k\)，其中 \(S_1\) 为栈底元素，\(S_k\) 为栈顶元素。

以单调递增栈为例，栈中元素满足:

\(S_1 < S_2 < ... < S_k\)

当需要插入新元素 \(x\) 时:

  • 当栈非空且 \(x < S_k\) 时，不断弹出栈顶元素
  • 直到栈空或 \(x \geq S_k\)
  • 将 \(x\) 压入栈中

通过这种方式，栈内元素始终保持单调性。每个元素最多入栈和出栈各一次，因此单调栈的时间复杂度为 \(O(n)\)。

例：看到牛头

第 \(i\) 头牛在队尾，第 \(N\) 头牛在队头，一个牛能向前看到连续的比它矮的牛的牛头，直到有一头牛比它高，再往前的牛头就看不到了。

求每头牛能看到的牛头的数量之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    身高
    ^
    |
15  |                          *
    |                          |
12  |  *                 *     |
    |  |                 |     |
10  |  |  *------------->|     |
    |  |  |       4      |     |
8   |  |  |        *     |     |
    |  |  |  *     |     |     |
6   |  |  |  |  *  |  *  |     |
    |  |  |  |  |  |  |  |     |
4   |  |  |  |  |  |  |  |  *  |
    |  |  |  |  |  |  |  |  |  |
2   |  |  |  |  |  |  |  |  |  |
    +--+--+--+--+--+--+--+--+--+---> 位置
    1  2  3  4  5  6  7  8  9  10

要快速计算每头牛的“视野”，就要快速知道它前面恰好比它高的最近的那个位置

维护一个单调栈，从\(N\)（队头）开始，序号从大到小逐个处理每头牛身高。

对第 \(i\) 头牛身高 h[i]，栈里小于 h[i]的都出栈，直到栈空或遇到一个比 h[i] 高的，这就是挡住第 \(i\) 头牛视线的牛，它俩之间就是 \(i\) 能看到的牛头个数。而栈里比 h[i] 低的这些，不会影响到 \(j < i\) 那些牛的视野，所以出栈。

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<string>
const int maxn = 8e4 + 10;
int n, h[maxn];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) {
        scanf("%d", &h[i]);
    }
    std::stack<int> st;
    long long ans = 0;
    for(int i = n - 1; i >= 0; i --) {
        while(!st.empty() && h[st.top()] < h[i]) {
            st.pop();
        }
        ans += st.empty() ? n - i - 1 : st.top() - i - 1;
        st.push(i);
    }
    printf("%lld\n", ans);
    return 0;
}

例：最大的矩形纸片

\(N\) 列，每列给出高度，求最大内部矩形

分析：每个柱子往一个方向延申，不一定是最优解。最大矩形至少在一根柱子上是抵到顶部的，考虑枚举每个柱子作为抵到顶部的柱子，看往左往右两个方向能延申多远。对于一个方向，单调栈已经可以搞定了，无非就是两个方向分别做一次单调栈。

对于这道题，单调栈维护的是栈底更低、栈顶更高的柱子，对每个位置 \(i\)，栈里比它高的都出栈——因为朝这个方向，比它高的不会影响延申，直到栈空或遇到比它低的，就是延申最远位置了，然后将 \(i\) 的高度入栈。

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<string>
const int maxn = 1e6 + 10;
int n, h[maxn], l_max[maxn];
int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) {
        scanf("%d", &h[i]);
    }
    std::stack<int> st_l;
    for(int i = 0; i < n; i ++) {
        while(!st_l.empty() && h[st_l.top()] >= h[i]) {
            st_l.pop();
        }
        // 以 i 为高度往左延申最大矩形长度
        l_max[i] = st_l.empty() ? i + 1 : i - st_l.top(); 
        st_l.push(i);
    }
    std::stack<int> st_r;
    long long ans = 0;
    for(int i = n - 1; i >= 0; i --) {
        while(!st_r.empty() && h[st_r.top()] >= h[i]) {
            st_r.pop();
        }
        // 以 i 为高度往右延申最大矩形长度
        int r_max = st_r.empty() ? n - i : st_r.top() - i;
        ans = std::max(ans, 1LL * (r_max + l_max[i] - 1) * h[i]);        
        st_r.push(i);
    }
    printf("%lld\n", ans);
    return 0;
}