单调栈：用一个栈，干掉所有「下一个更大」

栈里的元素始终保持有序，这个约束本身就是信息。

写在前面

「下一个更大的元素」「接雨水」「柱状图中的最大矩形」——这几道题第一次见很容易想到暴力，两层循环，O(n²)。

但如果你知道单调栈，这类题可以直接 O(n) 解决，而且代码并不复杂，难点只在于想清楚「栈里存什么」「什么时候弹出」。

单调栈是什么

单调栈就是普通的栈，但加了一个约束：栈内元素始终保持单调递增或单调递减的顺序。

每次要压入新元素时，先把栈顶里不满足单调性的元素弹出，再压入。被弹出的那一刻，就是信息被「提取」的时刻。

两种形态

单调递增栈（从栈底到栈顶递增）：

1
2
3
4
栈底 → 栈顶：小 → 大

压入元素时，弹出所有 >= 新元素 的栈顶
→ 被弹出时，新元素就是它「右边第一个更小的元素」

单调递减栈（从栈底到栈顶递减）：

1
2
3
4
栈底 → 栈顶：大 → 小

压入元素时，弹出所有 <= 新元素 的栈顶
→ 被弹出时，新元素就是它「右边第一个更大的元素」

一句话记忆

元素被弹出的那一刻，触发弹出的新元素就是它苦苦等待的「答案」。

例题讲解

例题一：每日温度（LeetCode 739）

给定一个整数数组 temperatures，对于每天，找出下一个温度更高的那天还要等几天。如果之后没有更高温度的天，填 0。

输入：temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
输出：[1, 1, 4, 2, 1, 1, 0, 0]

问题分析：

对每个位置，找右边第一个比它大的元素的位置差。暴力 O(n²)，单调栈 O(n)。

思路：

用单调递减栈（栈内温度从大到小）：

  • 栈里存下标，不存温度值（这样能算距离）
  • 遇到比栈顶温度更高的新元素，把栈顶弹出，答案就是当前下标减栈顶下标
  • 遍历完后，栈里剩下的元素说明后面没有更高温度，答案为 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> dailyTemperatures(vector<int>& temperatures) {
    int n = temperatures.size();
    vector<int> ans(n, 0);
    stack<int> st;  // 存下标，单调递减（栈顶温度最小）

    for (int i = 0; i < n; i++) {
        // 当前温度比栈顶更高，栈顶等到答案了
        while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
            int j = st.top(); st.pop();
            ans[j] = i - j;  // 等了 i-j 天
        }
        st.push(i);  // 当前下标入栈，等待右边更高温度
    }

    return ans;  // 没弹出的下标，ans 默认 0
}

执行过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
indices =       [0,  1,  2,  3,  4,  5,  6,  7]

i=0: 栈空，压入 0              栈: [0]        ans: [0,0,0,0,0,0,0,0]
i=1: 74>73，弹出 0，ans[0]=1-0=1  栈: []
     压入 1                    栈: [1]        ans: [1,0,0,0,0,0,0,0]
i=2: 75>74，弹出 1，ans[1]=2-1=1  栈: []
     压入 2                    栈: [2]        ans: [1,1,0,0,0,0,0,0]
i=3: 71<75，直接压入            栈: [2,3]
i=4: 69<71，直接压入            栈: [2,3,4]
i=5: 72>69，弹出 4，ans[4]=5-4=1
     72>71，弹出 3，ans[3]=5-3=2
     72<75，停止，压入 5        栈: [2,5]     ans: [1,1,0,2,1,0,0,0]
i=6: 76>72，弹出 5，ans[5]=6-5=1
     76>75，弹出 2，ans[2]=6-2=4
     栈空，压入 6              栈: [6]        ans: [1,1,4,2,1,1,0,0]
i=7: 73<76，直接压入            栈: [6,7]

遍历结束，栈中 [6,7] 未弹出，ans 保持 0

最终：[1, 1, 4, 2, 1, 1, 0, 0]

复杂度：

  • 时间：O(n)，每个元素最多入栈一次、出栈一次
  • 空间：O(n)，栈的空间

例题二：下一个更大元素 II（LeetCode 503）

给定一个循环数组，找每个元素的下一个更大元素。

输入：nums = [1, 2, 1]
输出：[2, -1, 2]（第 3 个 1 的下一个更大是开头的 2）

问题分析：

和 739 类似，但数组是循环的，最后几个元素要能「绕回来」看前面的元素。

思路：

把数组遍历两遍（下标对 n 取模模拟循环），但不需要真正复制数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> nextGreaterElements(vector<int>& nums) {
    int n = nums.size();
    vector<int> ans(n, -1);
    stack<int> st;  // 存下标

    for (int i = 0; i < 2 * n; i++) {  // 遍历两遍
        int idx = i % n;                // 循环下标
        while (!st.empty() && nums[idx] > nums[st.top()]) {
            ans[st.top()] = nums[idx];
            st.pop();
        }
        if (i < n) st.push(idx);  // 第二遍不再压入（避免重复）
    }

    return ans;
}

执行过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
nums = [1, 2, 1]，n=3

第一遍（i=0~2）：
i=0: idx=0，栈空，压入 0      栈: [0]
i=1: idx=1，2>1，弹出 0，ans[0]=2  栈: []
     压入 1                    栈: [1]
i=2: idx=2，1<2，压入 2       栈: [1,2]

第二遍（i=3~5，只弹不压）：
i=3: idx=0，nums[0]=1，1<2，没有弹出
i=4: idx=1，nums[1]=2，2>1（栈顶2），弹出 2，ans[2]=2
     2>1（下一栈顶1的值是2，2==2？不大于），停止
     此处 nums[1]=2，栈顶是 [1]，nums[1]=2 不大于 nums[1]=2，停止
i=5: idx=2，nums[2]=1，1<2，没有弹出

最终：[2, -1, 2]

复杂度：

  • 时间：O(n)
  • 空间：O(n)

例题三：柱状图中最大的矩形（LeetCode 84）

给定一个整数数组 heights 表示柱状图中各柱的高度，找出能勾勒出的最大矩形面积。

输入：heights = [2, 1, 5, 6, 2, 3]
输出：10

问题分析：

对每根柱子，想知道以它的高度为矩形高度，最远能向左、向右延伸到哪里——也就是找左边第一个比它矮的柱子、右边第一个比它矮的柱子。

这正是单调递增栈的用武之地：元素被弹出时，触发弹出的右边元素就是它右边第一个更矮的，栈中前一个元素就是它左边第一个更矮的。

思路：

在数组两端各加一个高度为 0 的哨兵，避免特判边界：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int largestRectangleArea(vector<int>& heights) {
    // 加头尾哨兵（高度为 0），保证所有元素最终都被弹出
    heights.insert(heights.begin(), 0);
    heights.push_back(0);

    int n = heights.size();
    int ans = 0;
    stack<int> st;  // 单调递增栈，存下标

    for (int i = 0; i < n; i++) {
        // 当前高度比栈顶更矮，栈顶找到了右边界
        while (!st.empty() && heights[i] < heights[st.top()]) {
            int h = heights[st.top()]; st.pop();  // 被弹出柱子的高度
            int left = st.top();                   // 左边界（栈中前一个）
            int width = i - left - 1;             // 宽度
            ans = max(ans, h * width);
        }
        st.push(i);
    }

    return ans;
}

为什么加哨兵？

  • 头部哨兵（高度 0）：确保任何柱子都能在左边找到比它矮的边界，不用特判空栈
  • 尾部哨兵（高度 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
加哨兵后 heights = [0, 2, 1, 5, 6, 2, 3, 0]
indices =          [0, 1, 2, 3, 4, 5, 6, 7]

i=0: h=0，栈空，压入 0        栈: [0]
i=1: h=2>0，压入 1            栈: [0,1]
i=2: h=1<2，弹出 1
     h=2，left=0，width=2-0-1=1，area=2*1=2，ans=2
     h=1>=h[0]=0，压入 2      栈: [0,2]
i=3: h=5>1，压入 3            栈: [0,2,3]
i=4: h=6>5，压入 4            栈: [0,2,3,4]
i=5: h=2<6，弹出 4
     h=6，left=3，width=5-3-1=1，area=6*1=6，ans=6
     h=2<5，弹出 3
     h=5，left=2，width=5-2-1=2，area=5*2=10，ans=10
     h=2>=h[2]=1，压入 5      栈: [0,2,5]
i=6: h=3>2，压入 6            栈: [0,2,5,6]
i=7: h=0<3，弹出 6
     h=3，left=5，width=7-5-1=1，area=3*1=3
     h=0<2，弹出 5
     h=2，left=2，width=7-2-1=4，area=2*4=8
     h=0<1，弹出 2
     h=1，left=0，width=7-0-1=6，area=1*6=6
     h=0>=h[0]=0，停止，压入 7

ans = 10

复杂度：

  • 时间：O(n)
  • 空间：O(n)

例题四：接雨水（LeetCode 42）

给定 n 个非负整数，每个数表示柱子的高度，计算下雨后能接到多少雨水。

输入：height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
输出：6

问题分析：

某个位置能接多少水，由它左边最高柱子和右边最高柱子中的较小者减去自身高度决定。暴力做法 O(n²)，有 O(n) 的双指针和单调栈两种解法，这里展示单调栈。

思路：

用单调递减栈（栈顶最小）：当发现新柱子比栈顶高，说明出现了一个「凹槽」，可以接水：

  • 弹出栈顶（凹槽底部）
  • 新的栈顶是左边界，当前下标是右边界
  • 宽度 = 右边界 - 左边界 - 1
  • 高度 = min(左边界高度, 右边界高度) - 凹槽底部高度
  • 面积 = 宽度 × 高度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int trap(vector<int>& height) {
    int ans = 0;
    stack<int> st;  // 单调递减栈，存下标

    for (int i = 0; i < (int)height.size(); i++) {
        while (!st.empty() && height[i] > height[st.top()]) {
            int bottom = st.top(); st.pop();  // 凹槽底部
            if (st.empty()) break;            // 没有左边界，接不了水

            int left = st.top();              // 左边界
            int width = i - left - 1;
            int h = min(height[left], height[i]) - height[bottom];  // 水的高度
            ans += width * h;
        }
        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
22
23
24
25
26
27
height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
idx =     [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11]

i=0: h=0，压入 0              栈: [0]
i=1: h=1>0，弹出 0（bottom）
     栈空，无左边界，break
     压入 1                    栈: [1]
i=2: h=0<1，压入 2            栈: [1,2]
i=3: h=2>0，弹出 2（bottom=0）
     left=1，width=3-1-1=1
     h=min(1,2)-0=1
     ans += 1*1=1              ans=1
     h=2>1，弹出 1（bottom=1）
     栈空，break
     压入 3                    栈: [3]
...（继续类似步骤，i=4 压入 4，i=5 压入 5，i=6 会先弹出 5，再压入 6）

关键步骤 i=7（h=3）：
  此时栈为 [3,4,6]，对应高度 [2,1,1]
  弹出 6（bottom=1）：left=4，right=7，width=7-4-1=2
  h=min(height[4], height[7]) - height[6] = min(1,3)-1 = 0，ans 不变
  弹出 4（bottom=1）：left=3，right=7，width=7-3-1=3
  h=min(height[3], height[7]) - height[4] = min(2,3)-1 = 1，ans += 3，变为 5
  继续弹出 3 后栈空，停止
  压入 7，栈: [7]

后续 i=10 时还能再接 1 格水，最终 ans = 6

复杂度：

  • 时间：O(n)
  • 空间：O(n)

双指针解法（补充）：

接雨水还有一个空间 O(1) 的双指针解法，思路不同但更简洁：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int trap(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int left_max = 0, right_max = 0;
    int ans = 0;

    while (left < right) {
        left_max = max(left_max, height[left]);
        right_max = max(right_max, height[right]);

        if (left_max < right_max) {
            ans += left_max - height[left];  // 由左边的矮墙决定
            left++;
        } else {
            ans += right_max - height[right]; // 由右边的矮墙决定
            right--;
        }
    }

    return ans;
}

两种方法都是 O(n)，双指针空间更优，单调栈思路更统一，面试时能说出两种更好。

容易踩的坑

1. 栈里存下标，不存值

很多题需要计算宽度（位置差），所以栈里要存下标，通过下标找到对应的值。初学容易直接存值导致算不出距离。

1
2
3
4
5
// ❌ 只存值，算不出位置差
stack<int> st;  // 存的是 heights[i]

// ✅ 存下标，需要值时通过 heights[st.top()] 获取
stack<int> st;  // 存的是 i

2. 弹出后别忘了判断栈是否为空

LeetCode 84 和 42 里，弹出元素后要找「前一个」作为左边界，但这时栈可能已经空了，要先判断。

1
2
3
int bottom = st.top(); st.pop();
if (st.empty()) break;  // 没有左边界，跳过
int left = st.top();

3. 递增栈 vs 递减栈

目标 栈的类型 被弹出的时机
找右边第一个更大的 单调递减栈 压入更大元素时
找右边第一个更小的 单调递增栈 压入更小元素时
最大矩形面积 单调递增栈 压入更小高度时
接雨水 单调递减栈 压入更大高度时

判断的时候想一句：「我什么时候能知道某个元素的答案？」—— 就是它被弹出的那一刻。

4. 取等号的问题

弹出条件用 > 还是 >= 会影响「相等元素要不要保留在栈里」：

  • >：遇到相等不弹，保留旧元素，适合把相等值也当作潜在边界的写法
  • >=：遇到相等也弹，适合希望边界保持严格更小 / 更大、避免重复计算的写法

关键不是“结果不对就试一下”，而是先想清楚：相等元素在这道题里算不算有效边界。

总结

mindmap
  root((单调栈))
    核心思想
      栈内保持单调性
      被弹出时提取答案
      每个元素最多入栈出栈各一次 O(n)
    两种栈
      单调递减栈
        找右边第一个更大
        接雨水
      单调递增栈
        找右边第一个更小
        最大矩形面积
    经典题目
      739 每日温度
      503 下一个更大元素II 循环数组
      84 柱状图最大矩形
      42 接雨水
    常见陷阱
      栈存下标不存值
      弹出后检查栈是否为空
      递增递减选错
      哨兵简化边界处理

各题对比：

题目 栈类型 弹出条件 弹出时计算
739 每日温度 递减 新元素更大 距离差
503 下一个更大 递减 新元素更大 新元素值
84 最大矩形 递增 新元素更小 高 × 宽
42 接雨水 递减 新元素更大 凹槽面积

单调栈的核心就是一句话：让每个元素在被弹出的时候，告诉你它想告诉你的信息。 想清楚「什么时候弹」「弹出时能知道什么」，这类题基本上就拿下了。

推荐阅读：