单调栈

一句话算法

单调栈把“还没找到答案”的元素留在栈里，新元素一来就结算所有被它淘汰的旧元素。

问题模型

单调栈常用来处理“离当前位置最近的第一个更大/更小元素”。

例如给定序列：

对每个位置 $i$，求它右侧第一个满足：

的位置 $j$。如果不存在，答案为 $0$。

暴力枚举每个 $i$ 的右侧元素需要 $O(n^2)$。单调栈让每个元素最多入栈一次、出栈一次，总复杂度为 $O(n)$。

核心直觉

从左到右扫描。

栈里保存的是“还没有找到右侧第一个更大元素”的位置。

当新元素 a[i] 到来时：

• 如果 a[i] 比栈顶元素大，说明栈顶的答案就是 i；
• 栈顶结算并弹出；
• 继续比较新的栈顶；
• 直到栈顶不小于 a[i]，再把 i 入栈。

求右侧第一个更大元素时，栈内值保持单调不增：

栈底 -> 栈顶
大    ... 小

新来的大元素会把右侧一串更小的元素全部结算掉。

状态与维护规则

栈中存下标，不直接存值。这样既能比较 a[index]，又能给 ans[index] 赋值。

求右侧第一个更大元素：

        
1
2
3
4
5

        while (!st.empty() && a[st.top()] < a[i]) {
    ans[st.top()] = i;
    st.pop();
}
st.push(i);
    

如果题目要求：

• 右侧第一个大于等于：把 < 改成 <=；
• 右侧第一个更小：反过来维护单调不减栈；
• 左侧第一个更大/更小：从左到右扫描时，在入栈前读栈顶；或从右到左对称处理。

算法步骤

1. 初始化空栈。
2. 从左到右枚举位置 i。
3. 当栈非空且 a[栈顶] < a[i] 时：
   • ans[栈顶] = i；
   • 弹出栈顶。
4. 把 i 入栈。
5. 扫描结束后，栈中剩下的位置右侧没有更大元素，答案保持 0。

算法证明

核心不变量：处理完位置 $i$ 后，栈中保存的都是前 $i$ 个元素里尚未找到右侧第一个更大元素的位置，并且栈中对应值单调不增。

1. 入栈含义正确

   新位置 $i$ 刚被扫描时，它右侧还没有被扫描，所以暂时找不到答案，应入栈等待。

2. 弹栈结算正确

   当 $a_i>a_j$ 且 $j$ 在栈顶时，说明从 $j+1$ 到 $i-1$ 之间没有任何元素能让 $j$ 出栈。

   因此这些元素都不大于 $a_j$，更不可能是 $j$ 的答案。当前 $i$ 就是 $j$ 右侧第一个更大元素。

3. 未弹出的元素仍需等待

   如果栈顶元素 $a_j \ge a_i$，那么 $i$ 不能作为 $j$ 的更大元素。$j$ 继续留在栈里等待后面的元素。

4. 复杂度线性

   每个位置只入栈一次，最多出栈一次，所以总操作次数为 $O(n)$。

因此单调栈算法正确。

复杂度分析

设序列长度为 $n$。

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

代码实现

下一个更大元素：

        
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

        #include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1), ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 栈中保存还没有找到右侧第一个更大元素的位置。
    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] < a[i]) {
            ans[st.back()] = i;
            st.pop_back();
        }
        st.push_back(i);
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i == n ? '\n' : ' ');
    }
    return 0;
}
    

直方图最大矩形：

        
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

        #include <bits/stdc++.h>
using namespace std;

int main() {
    while (true) {
        int n;
        cin >> n;
        if (n == 0) break;

        vector<long long> h(n + 2, 0);
        for (int i = 1; i <= n; i++) {
            cin >> h[i];
        }

        long long ans = 0;
        vector<int> st;
        st.push_back(0);

        for (int i = 1; i <= n + 1; i++) {
            while (!st.empty() && h[st.back()] > h[i]) {
                int mid = st.back();
                st.pop_back();
                long long height = h[mid];
                long long width = i - st.back() - 1;
                ans = max(ans, height * width);
            }
            st.push_back(i);
        }

        cout << ans << "\n";
    }
    return 0;
}
    

测试用例

下一个更大元素输入：

5
1 4 2 3 5

输出：

2 5 4 5 0

直方图最大矩形输入：

7
2 1 4 5 1 3 3
0

输出：

8

应用分类详解

单调栈的本质是：在一维序列中维护一批尚未被新元素“截断”的候选。只要题目问“最近的第一个更大/更小元素”，或某个元素能向左/向右扩展到哪里，就应该考虑单调栈。

一、下一个更大或更小元素

典型模式： 对每个位置，找左侧或右侧第一个比它大/小的位置。

识别信号： 出现“第一个更大”“最近更小”“右边第一个比它高”。

核心建模： 栈中保存还没找到答案的位置，新元素负责结算被它超过的栈顶元素。

二、扩展边界

典型模式： 每个元素作为最小值或最大值，向左右能扩展到哪里。

识别信号： 出现“以某个高度为限制”“连续区间内它是最小值”“矩形最大面积”。

核心建模： 对每个位置求左侧第一个更小和右侧第一个更小，确定它能控制的区间。

三、贡献统计

典型模式： 每个元素作为区间最小值或最大值，对多少个区间产生贡献。

识别信号： 出现“所有子数组最小值之和”“每个元素作为最值的次数”。

核心建模： 用单调栈求出每个元素作为最值能覆盖的左右边界，贡献为值乘以左右选择数。

经典例题

1. luogu-P5788

单调栈模板题。重点是栈里保存还没有找到答案的位置。

2. roj-3032

直方图中最大的矩形。用单调递增栈，在遇到更矮柱子时结算被弹出柱子的最大宽度。

3. LeetCode 739

每日温度。答案从“位置”变成“距离”，本质仍是右侧第一个更大元素。

参考

• 本文旧版解析保留的核心思路：去除已经得到答案的点，剩下的候选自然形成单调结构。