单调栈

一句话算法

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

问题模型

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

例如给定序列：

对每个位置 $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

        # 单调栈求每个元素右侧第一个更大元素的下标。
# a 为 1 下标（a[0] 占位不用），返回 ans 也是 1 下标，ans[i] 为下标值、0 表示不存在。
# 栈中保存还没找到右侧更大元素的位置；a[st.back()] 从栈底到栈顶严格递减。
# 弹出时机：a[i] 大于栈顶对应值时，栈顶元素右侧第一个更大元素就是 i。
# 调用示例：next_greater([0, 2, 1, 3]) -> [0, 3, 3, 0]

type Arr = list[int]  # 1 下标数组，a[0] / ans[0] 占位不用


def next_greater(a: Arr) -> Arr:
    """返回长度 n+1 的 ans（1 下标），ans[i] = 右侧第一个更大元素下标，不存在为 0。"""
    n = len(a) - 1
    ans = [0] * (n + 1)
    st: Arr = []  # 栈内是下标，对应值单调不增

    for i in range(1, n + 1):
        while st and a[st[-1]] < a[i]:
            ans[st[-1]] = i
            st.pop()
        st.append(i)

    return ans
    

直方图最大矩形：

        
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;
}
    

        
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

        # 单调栈求直方图最大矩形面积。
# h 为 1 下标高度数组（h[1..n]），要求高度非负；函数内部按 C++ 版补齐 h[0] = h[n+1] = 0 两个哨兵。
# 对每个柱子 mid，左右两端第一个比它矮的柱子夹出的宽度就是它能撑起的最大宽度；
# 用递增单调栈，遇到更矮的 h[i] 时弹出并结算 mid 的面积。
# C++ 用 long long 防 height * width 溢出 int；Python int 任意精度，该坑不存在。
# 调用示例：largest_rectangle([0, 2, 1, 5, 6, 2, 3]) -> 10

type Arr = list[int]  # 1 下标数组，h[0] 占位不用


def largest_rectangle(h: Arr) -> int:
    """返回直方图中最大矩形面积；h 长度至少为 1（n = len(h) - 1，n = 0 时返回 0）。"""
    n = len(h) - 1

    # 复制成 n+2 长度并补上左右哨兵 0：保证栈底恒有 h[0]=0 兜底，且最后 i=n+1 能弹空栈。
    hs = [0] * (n + 2)
    for i in range(1, n + 1):
        hs[i] = h[i]

    answer = 0
    st: Arr = [0]  # 栈内存下标，对应高度单调不减

    for i in range(1, n + 2):
        while hs[st[-1]] > hs[i]:
            mid = st.pop()
            height = hs[mid]
            width = i - st[-1] - 1  # 左右第一个更矮柱子之间的宽度
            area = height * width
            if area > answer:
                answer = area
        st.append(i)

    return answer
    

测试用例

下一个更大元素输入：

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

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

参考

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