单调栈 - 面试完全指南

概述

单调栈 是一种强大的算法模式，专门解决一类问题：为数组中每个位置找到 下一个更大/更小元素。它是面试热门考点，因为它能把 $O(n^2)$ 的暴力解法优化成优雅的 $O(n)$ 算法。

为什么面试官喜欢考单调栈

考察模式识别能力 - 识别何时应用这个技巧是关键
需要仔细思考 - 决定使用递增栈还是递减栈
进阶难题的基础 - 柱状图和接雨水是经典难题
高效且优雅 - 展示你能超越暴力解法进行优化

什么是单调栈？

单调栈 维护元素的严格递增或严格递减顺序。当新元素打破这个顺序时，我们弹出元素直到恢复顺序。

直观理解

单调递减栈（用于找下一个更大元素）:

数组: [2, 1, 5, 6, 2, 3]

第 1 步: 处理 2
        栈: [2]
        
第 2 步: 处理 1
        1 < 2，入栈
        栈: [2, 1]
        
第 3 步: 处理 5
        5 > 1，弹出 1 → 1 的下一个更大元素是 5
        5 > 2，弹出 2 → 2 的下一个更大元素是 5
        栈: [5]
        
第 4 步: 处理 6
        6 > 5，弹出 5 → 5 的下一个更大元素是 6
        栈: [6]
        
第 5 步: 处理 2
        2 < 6，入栈
        栈: [6, 2]
        
第 6 步: 处理 3
        3 > 2，弹出 2 → 2 的下一个更大元素是 3
        3 < 6，入栈
        栈: [6, 3]

栈中剩余: 6 和 3 没有下一个更大元素

核心洞察

每个元素最多入栈一次、出栈一次，所以时间复杂度是 $O(n)$ 。

两种核心模式

模式一：下一个更大元素（单调递减栈）

当需要找 下一个更大 元素时，使用 单调递减 栈。

弹出条件: current > stack.top()
结果: 栈中元素找到 current 作为它们的下一个更大元素

模式二：下一个更小元素（单调递增栈）

当需要找 下一个更小 元素时，使用 单调递增 栈。

弹出条件: current < stack.top()
结果: 栈中元素找到 current 作为它们的下一个更小元素

快速参考表

问题类型	栈类型	弹出条件	找到什么
下一个更大	递减栈	`current > top`	右边第一个更大
下一个更小	递增栈	`current < top`	右边第一个更小
上一个更大	递减栈	`current >= top`	左边第一个更大
上一个更小	递增栈	`current <= top`	左边第一个更小

题目一：下一个更大元素 I (LC 496)

问题描述

给你两个整数数组 nums1 和 nums2，其中 nums1 是 nums2 的子集。对于 nums1 中的每个元素，在 nums2 中找到下一个更大元素。如果不存在则返回 -1。

示例：

nums1 = [4,1,2]，nums2 = [1,3,4,2]
输出：[-1,3,-1]
解释：4 没有下一个更大元素，1 的下一个更大是 3，2 没有下一个更大元素

两种解法

这道题有两种遍历方向，各有各的思维方式：

方法	方向	栈中存储	核心思想
从左往右	正向遍历	等待答案的元素	当前元素是较小栈元素的”答案”
从右往左	逆向遍历	候选答案	栈顶是当前元素的答案

方法一：从左往右（正向遍历）

思路：从左往右遍历。当遇到一个元素时，它成为所有比它小的栈中等待元素的”下一个更大元素”。

数组: [1, 3, 4, 2]

i=0: 处理 1，栈空 → 入栈 1
     栈: [1]
     
i=1: 处理 3，3 > 1 → 弹出 1，记录 nextGreater[1] = 3
     入栈 3
     栈: [3]
     
i=2: 处理 4，4 > 3 → 弹出 3，记录 nextGreater[3] = 4
     入栈 4
     栈: [4]
     
i=3: 处理 2，2 < 4 → 入栈 2
     栈: [4, 2]

结果: 4 和 2 没有下一个更大元素（留在栈中）

自己动手试一试（从左往右）：

Initializing...

方法二：从右往左（逆向遍历）

思路：从右往左遍历。栈中维护的是”候选答案”。如果栈顶存在且比当前元素大，那就是答案。

数组: [1, 3, 4, 2]

i=3: 处理 2，栈空 → nextGreater[2] = -1，入栈 2
     栈: [2]
     
i=2: 处理 4，4 > 2 → 弹出 2（不可能是任何人的答案）
     栈空 → nextGreater[4] = -1，入栈 4
     栈: [4]
     
i=1: 处理 3，3 < 4 → nextGreater[3] = 4，入栈 3
     栈: [4, 3]
     
i=0: 处理 1，1 < 3 → nextGreater[1] = 3，入栈 1
     栈: [4, 3, 1]

结果: 答案一样，思路不同！

自己动手试一试（从右往左）：

Initializing...

两种方法对比

对比点	从左往右	从右往左
何时得到答案	找到更大元素时	立即得到当前元素答案
栈的角色	”等候室”：存放未找到答案的	”候选池”：存放可能的答案
思维模型	”这个元素能帮到谁？"	"谁能帮到这个元素？“
弹出条件	`栈顶 < 当前`	`栈顶 <= 当前`

两种方法的时间和空间复杂度相同。选择哪种取决于你觉得哪种思路更自然！

复杂度分析

时间: $O(n + m)$ ，其中 n = len(nums1)，m = len(nums2)
空间: $O(m)$ 用于哈希表和栈

题目二：下一个更大元素 II (LC 503)

问题描述

给定一个循环数组，找出每个位置的下一个更大元素。数组是循环的，最后一个元素后面是第一个元素。

示例：

输入：[1,2,1]
输出：[2,-1,2]
解释：索引 2 处的元素（值为 1）绕回去在索引 1 找到了 2

解题思路

技巧：遍历数组两遍来模拟循环。

数组: [1, 2, 1]
处理: [1, 2, 1, 1, 2, 1]  (虚拟拼接)
               ↑ 只在第一遍入栈

代码实现

为什么要遍历两遍？

第一遍：构建部分结果，所有索引入栈
第二遍：栈中剩余元素有机会找到它们的下一个更大元素

复杂度分析

时间: $O(n)$ - 每个元素最多处理两次
空间: $O(n)$ - 栈可能存储所有索引

题目三：每日温度 (LC 739)

问题描述

给定每日温度数组，返回需要等待多少天才能遇到更暖的温度。如果没有更暖的天，返回 0。

示例：

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

解题思路

这是”下一个更大元素”问题，只是返回距离而不是值。

第 0 天 (73°): 下一个更暖是第 1 天 (74°) → 等待 1 天
第 2 天 (75°): 下一个更暖是第 6 天 (76°) → 等待 4 天

代码实现

交互式可视化

Initializing...

与下一个更大元素的区别

栈中存储索引（不是值）
结果是 currentIndex - poppedIndex

复杂度分析

时间: $O(n)$
空间: $O(n)$

题目四：柱状图中最大矩形 (LC 84)

问题描述

给定一个表示柱状图的高度数组，找出最大矩形的面积。

     ██
  ██ ██
  ██ ██ ██
██ ██ ██ ██
heights = [2,1,5,6,2,3]
答案 = 10 (高度 5，宽度 2 的矩形)

解题思路

对于每个柱子，我们想知道：

它能向左延伸多远（直到遇到更矮的柱子）
它能向右延伸多远（直到遇到更矮的柱子）

单调栈通过追踪柱子何时无法继续延伸来高效地找到这两个边界。

核心洞察

当我们弹出一个柱子（因为当前柱子更矮）时，我们知道：

右边界：当前索引
左边界：弹出后的栈顶
高度：被弹出柱子的高度

弹出索引 i 的柱子（当 heights[i] > 当前值）:
  width = current_index - stack_top - 1
  area = height[i] * width

代码实现

示例演示

heights = [2, 1, 5, 6, 2, 3, 0(哨兵)]

i=0: push 0, stack=[0]
i=1: 1 < 2, pop 0, area=2*1=2, push 1, stack=[1]
i=2: push 2, stack=[1,2]
i=3: push 3, stack=[1,2,3]
i=4: 2 < 6, pop 3, area=6*1=6
     2 < 5, pop 2, area=5*2=10
     push 4, stack=[1,4]
i=5: push 5, stack=[1,4,5]
i=6: 0 < all, pop 5, area=3*1=3
     pop 4, area=2*4=8
     pop 1, area=1*6=6

最大面积 = 10

复杂度分析

时间: $O(n)$
空间: $O(n)$

📖 更详细的解法可以查看柱状图中最大的矩形 - 三种解法与交互式可视化。

题目五：接雨水 (LC 42)

问题描述

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

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6（接住的雨水单位）

核心思路

雨水只能被困在左右两侧都有更高柱子的凹槽中。关键在于识别这些”凹槽”并计算每个凹槽能接多少水。

为什么需要单调递减栈？

想象一下，当我们从左往右遍历时：

如果遇到一个比栈顶更高的柱子，说明可能形成了一个凹槽
栈顶的柱子就是凹槽的底部
栈中第二个元素（新栈顶）是左墙
当前柱子是右墙

详细分析过程

让我们用一个具体例子来理解：height = [0, 1, 0, 2, 1, 0, 1, 3]

步骤 1：初始化

栈：[]（空）
总水量：0

步骤 2：处理索引 0（高度 0）

当前：height[0] = 0
栈为空，直接压入：stack = [0]
说明：高度为 0 的柱子不能形成凹槽，但可以作为潜在的左墙

步骤 3：处理索引 1（高度 1）

当前：height[1] = 1
1 > 0（栈顶），弹出 0
栈为空，无法形成凹槽（没有左墙）
压入 1：stack = [1]
关键理解：弹出后栈为空，说明没有左墙，无法接水

步骤 4：处理索引 2（高度 0）

当前：height[2] = 0
0 < 1（栈顶），不弹出，直接压入：stack = [1, 2]
说明：栈保持单调递减，[1, 0] 表示一个潜在的凹槽

步骤 5：处理索引 3（高度 2）——关键步骤

当前：height[3] = 2
2 > 0（栈顶），形成凹槽！
弹出 2（底部）：bottom = 2, height[2] = 0
栈顶 1 是左墙：left = 1, height[1] = 1
当前 3 是右墙：right = 3, height[3] = 2
计算水量：
- 水高 = min(height[1], height[3]) - height[2] = min(1, 2) - 0 = 1
- 宽度 = 3 - 1 - 1 = 1
- 水量 = 1 × 1 = 1
- 总水量：0 + 1 = 1
压入 3：stack = [1, 3]
关键理解：凹槽由左墙（索引1）、底部（索引2）、右墙（索引3）组成

步骤 6：处理索引 4（高度 1）

当前：height[4] = 1
1 < 2（栈顶），不弹出，直接压入：stack = [1, 3, 4]

步骤 7：处理索引 5（高度 0）

当前：height[5] = 0
0 < 1（栈顶），不弹出，直接压入：stack = [1, 3, 4, 5]

步骤 8：处理索引 6（高度 1）

当前：height[6] = 1
1 > 0（栈顶），形成凹槽！
弹出 5（底部）：bottom = 5, height[5] = 0
左墙：left = 4, height[4] = 1
右墙：right = 6, height[6] = 1
计算水量：
- 水高 = min(1, 1) - 0 = 1
- 宽度 = 6 - 4 - 1 = 1
- 水量 = 1 × 1 = 1
- 总水量：1 + 1 = 2
1 < 1（新栈顶），不继续弹出
压入 6：stack = [1, 3, 4, 6]

步骤 9：处理索引 7（高度 3）——重要步骤

当前：height[7] = 3
3 > 1（栈顶），形成多个凹槽！
弹出 6（底部）：bottom = 6, height[6] = 1
左墙：left = 4, height[4] = 1
右墙：right = 7, height[7] = 3
水高 = min(1, 3) - 1 = 0，水量 = 0（没有水）
继续弹出 4（底部）：bottom = 4, height[4] = 1
左墙：left = 3, height[3] = 2
右墙：right = 7, height[7] = 3
水高 = min(2, 3) - 1 = 1
宽度 = 7 - 3 - 1 = 3
水量 = 1 × 3 = 3
总水量：2 + 3 = 5
继续弹出 3（底部）：bottom = 3, height[3] = 2
左墙：left = 1, height[1] = 1
右墙：right = 7, height[7] = 3
水高 = min(1, 3) - 2 = -1（负数，不接水）
压入 7：stack = [1, 7]

最终结果：总水量 = 5

算法要点总结

栈的作用：维护一个单调递减栈，存储索引
何时弹出：当 height[i] > height[stack.top()] 时，说明找到了右墙
如何计算：
- 弹出底部后，新栈顶是左墙
- 水高 = min(左墙高度, 右墙高度) - 底部高度
- 宽度 = 右墙索引 - 左墙索引 - 1
- 水量 = 水高 × 宽度
边界情况：弹出后栈为空，说明没有左墙，无法接水

交互式可视化

使用下面的可视化工具，你可以看到每一步的详细过程：

初始化中...

代码实现

代码逐行解析

以 Java 代码为例：

Deque<Integer> stack = new ArrayDeque<>();  // 单调递减栈，存储索引
int water = 0;  // 总水量

for (int i = 0; i < height.length; i++) {
    // 当遇到比栈顶更高的柱子时，可能形成凹槽
    while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
        int bottom = stack.pop();  // 弹出凹槽底部
        
        if (stack.isEmpty()) break;  // 没有左墙，无法接水
        
        int left = stack.peek();  // 左墙索引
        // 计算水高：左右墙的较小值减去底部高度
        int h = Math.min(height[left], height[i]) - height[bottom];
        // 计算宽度：右墙索引减去左墙索引再减1
        int w = i - left - 1;
        // 累加水量
        water += h * w;
    }
    stack.push(i);  // 压入当前索引
}

关键点：

height[stack.peek()] < height[i]：当前柱子比栈顶高，形成凹槽
stack.isEmpty()：弹出后栈为空，没有左墙
Math.min(height[left], height[i])：水高由较矮的墙决定
i - left - 1：宽度不包括左右墙本身

替代方法：双指针

还有一种空间复杂度 O(1) 的双指针方法：

def trap(self, height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

复杂度分析

栈方法：

时间: $O(n)$
空间: $O(n)$

双指针：

时间: $O(n)$
空间: $O(1)$

模板与套路

模板一：下一个更大元素

def nextGreater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # 索引
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

模板二：下一个更小元素

def nextSmaller(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # 索引
    
    for i in range(n):
        while stack and nums[stack[-1]] > nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

模板三：循环数组

def nextGreaterCircular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(2 * n):  # 遍历两遍
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    
    return result

模板四：柱状图/面积问题

def histogramPattern(heights):
    stack = []
    result = 0
    
    for i, h in enumerate(heights + [0]):  # 哨兵
        while stack and heights[stack[-1]] > h:
            popped = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            result = max(result, heights[popped] * width)
        stack.append(i)
    
    return result

复杂度分析

题目	时间	空间
下一个更大元素 I	O(n+m)	O(n)
下一个更大元素 II	O(n)	O(n)
每日温度	O(n)	O(n)
柱状图中最大矩形	O(n)	O(n)
接雨水（栈）	O(n)	O(n)
接雨水（双指针）	O(n)	O(1)

为什么是 O(n)？

每个元素最多入栈一次、出栈一次。虽然 for 循环里有 while 循环，但总操作次数不超过 2n。

面试技巧

模式识别

问自己这些问题：

“我是在找 下一个更大/更小 元素吗？”
“我需要的是距离还是值？”
“数组是循环的吗？”
“我在计算面积还是容量？“

常见错误

栈类型错误：该用递增栈时用了递减栈（或反之）
忘记存索引：需要距离的问题要存索引而不是值
循环数组：记住遍历两遍但只在第一遍入栈
哨兵值：柱状图问题忘记在末尾加 0

可能的追问

“能用 O(1) 空间吗？“（接雨水 → 双指针）
“有重复元素怎么办？” → 需要时用 <= 代替 <
“二维柱状图呢？” → 对每行应用一维柱状图算法（LC 85）

如何讲解

说明模式：“这是一个下一个更大元素问题”
解释栈类型：“我用单调递减栈因为…”
用例子演示：在小输入上展示入栈/出栈操作
分析复杂度：“每个元素入栈/出栈一次，所以是 O(n)“

总结

单调栈的关键要点：

两种模式：递减栈找下一个更大，递增栈找下一个更小
存储索引：当需要距离或位置时
循环数组：遍历两遍，只在第一遍入栈
柱状图问题：用哨兵值（0）触发最后的弹出
O(n) 保证：每个元素最多入栈出栈一次

掌握这些模式，你就能在面试中一眼识别单调栈问题！