1. 什么时候想到单调栈
单调栈最擅长解决的是:对每个元素,寻找某一侧第一个比它更大或更小的元素。
如果直接从每个位置向后扫描,最坏需要 O(n^2);单调栈把还没有找到答案的位置暂时保存起来,等到一个能够解决它们的新元素出现时,再批量结算。
常见题目信号:
| 题目描述 | 单调栈要寻找的关系 |
|---|---|
| 还要等几天才会更暖 | 右侧第一个严格更大的元素 |
| 下一个更大元素 | 右侧第一个严格更大的元素 |
| 下一个更小元素 | 右侧第一个严格更小的元素 |
| 每根柱子能向左右延伸多远 | 左右第一个更矮的柱子 |
| 凹槽能够装多少水 | 当前低点左右的挡板 |
| 子数组最小值或最大值贡献 | 每个元素作为最值的左右边界 |
单调栈通常不是为了模拟入栈、出栈本身,而是利用栈顶表示离当前位置最近、并且仍在等待答案的候选位置。
它和几个相近结构的区别:
| 数据结构 | 主要解决什么问题 | 过期元素怎样离开 |
|---|---|---|
| 普通栈 | 括号匹配、表达式、撤销、路径 | 由业务顺序决定 |
| 单调栈 | 最近更大或更小、左右边界 | 被当前元素破坏单调性时弹出 |
| 单调队列 | 固定滑动窗口中的最大值或最小值 | 队首过期、队尾失去竞争力 |
| 堆 | 动态集合中的全局最大值或最小值 | 删除堆顶,或惰性删除 |
2. 单调性到底怎样维护
2.1 栈里优先保存下标
大多数题目应该保存下标,而不是只保存数值:
1 | stack = [index1, index2, ...] |
通过下标可以同时得到:
- 元素值:
nums[stack[-1]] - 距离:
current - stack[-1] - 左右边界:弹出后查看新的
stack[-1] - 正确处理重复值:相同数值处在不同位置,答案可能不同
只有题目保证元素互不相同,并且只需要返回对应数值时,才适合直接保存数值。
2.2 栈的名称按“栈底到栈顶”的数值顺序描述
寻找右侧第一个严格更大元素时,栈内数值从栈底到栈顶保持非递增:
1 | 栈底 [大, ..., 小] 栈顶 |
一个更大的当前值到来后,会不断弹出栈顶较小值;这些被弹出的下标终于找到了右侧第一个更大元素。
严格与非严格关系决定相等元素是否弹出:
| 要找的答案 | 栈底到栈顶 | 弹出条件 |
|---|---|---|
| 下一个严格更大 | 非递增,相等可共存 | stack_top < current |
| 下一个大于等于 | 严格递减 | stack_top <= current |
| 下一个严格更小 | 非递减,相等可共存 | stack_top > current |
| 下一个小于等于 | 严格递增 | stack_top >= current |
不要只背“递增栈找更大”或“递减栈找更大”。不同资料可能按栈顶观察方向命名,容易产生歧义;直接写出栈底到栈顶的关系和 while 条件更可靠。
2.3 每个下标只会入栈一次、出栈一次
代码里虽然有嵌套的 while,但一个下标一旦弹出就不会再次进入同一个栈:
1 | 每个下标入栈最多 1 次 |
因此一次完整扫描的时间复杂度是 O(n),栈的空间复杂度是 O(n)。这叫摊还分析,不是把内外循环简单相乘成 O(n^2)。
3. 一套统一的“下一个严格更大”模板
先写一个返回下标的通用版本:
1 | def next_strictly_greater_indices(nums: list[int]) -> list[int]: |
下面用 nums = [2, 1, 2, 4, 3] 把模板逐句展开。这个例子特意放了两个相等的 2:当当前值也是 2 时,2 < 2 为假,所以旧的 2 仍要留在栈中;直到 4 到来,它们才依次找到答案。
for current in range(len(nums))
while stack and nums[stack[-1]] < nums[current]
waiting = stack.pop(); answer[waiting] = current
stack.append(current)
理解模板时只看两个角色:
1 | waiting:过去出现、仍在等待答案的下标 |
从这个模板可以直接改出不同返回形式:
1 | 返回更大元素的下标:answer[waiting] = current |
遍历结束后仍留在栈中的位置,说明右侧不存在符合条件的元素,因此保留初始化答案,例如 -1 或 0。
写题前先回答四个问题:
- 栈里保存下标还是数值?
- 谁在等待答案,谁触发结算?
- 要找严格更大、更大等于、严格更小,还是更小等于?
- 找不到答案时应该返回
-1、0还是数组边界?
4. 739. 每日温度:单调栈入门题
题目要求每一天距离右侧第一个更高温度还有几天,因此:
1 | 栈中保存仍未找到更暖日期的下标 |
1 | def daily_temperatures(temperatures: list[int]) -> list[int]: |
以 [73, 74, 75, 71, 69, 72, 76, 73] 为例:
| 当前温度 | 发生的出栈 | 结算结果 | 处理后的待定温度 |
|---|---|---|---|
| 73 | 无 | 无 | [73] |
| 74 | 73 | 第 0 天等待 1 天 | [74] |
| 75 | 74 | 第 1 天等待 1 天 | [75] |
| 71 | 无 | 无 | [75, 71] |
| 69 | 无 | 无 | [75, 71, 69] |
| 72 | 69、71 | 第 4 天等 1 天,第 3 天等 2 天 | [75, 72] |
| 76 | 72、75 | 第 5 天等 1 天,第 2 天等 4 天 | [76] |
| 73 | 无 | 无 | [76, 73] |
相同温度不算“更暖”,所以判断条件必须是:
1 | temperatures[stack[-1]] < temperature |
如果写成 <=,相同温度也会被错误地当成答案。最后仍在栈里的日期右侧没有更高温度,答案保持为 0。
5. 下一个更大元素
5.1 496. 下一个更大元素 I:先处理全集,再回答子集
nums1 是 nums2 的子集,并且元素互不相同。可以先扫描 nums2,记录每个数的下一个更大元素,再按 nums1 的顺序取答案:
1 | def next_greater_element( |
这里可以直接保存数值,是因为题目保证 nums2 中所有整数互不相同。如果允许重复值,value -> answer 无法区分不同位置,应该改成保存下标。
5.2 503. 下一个更大元素 II:用取模模拟环形数组
环形数组中,末尾元素还可以继续查看数组开头。把下标范围扫描两遍,就相当于把数组复制了一份:
1 | def next_greater_elements(nums: list[int]) -> list[int]: |
第二遍不要再次把下标入栈,否则同一个位置会重复等待答案,既增加无效操作,也让状态难以解释。
取模只是模拟访问顺序:
1 | step:0, 1, ..., n-1, n, ..., 2n-1 |
6. 42. 接雨水:弹出的是凹槽底部
接雨水使用单调栈时,栈中保存尚未找到右侧挡板的柱子下标。当前柱子比栈顶更高,说明出现了右挡板,可以按水平方向计算一层积水。
弹出一个凹槽底部 bottom 后:
1 | right = 当前下标 |
1 | def trap(height: list[int]) -> int: |
下面用 height = [4, 2, 0, 3, 2, 5] 按栈的实际结算顺序画出地形。黑色矩形是柱子,蓝色方格是已经计算出的水;每次弹出 bottom 后,图中会标出 left、bottom 和 right,再把这一层水横向填进去。
height = [4, 2, 0, 3, 2, 5]
for right, right_height in enumerate(height)
while stack and height[stack[-1]] < right_height
bottom = stack.pop()
if not stack: break
left = stack[-1]; water += width * bounded_height
stack.append(right)
这里最容易错的地方:
bottom弹出以后,新的栈顶才是左挡板。- 弹出后栈为空,说明没有左挡板,必须停止当前轮计算。
- 宽度不包含左右挡板,所以是
right - left - 1。 - 水位由较矮挡板决定,所以使用
min(left_height, right_height)。 - 一次弹出计算的是一层横向积水,不是某一根柱子上方的全部水量。
二维扩展题 407. 接雨水 II 不能再只看左右两根挡板:水可能从上下左右任意方向流走。它需要用小根堆维护整圈最低边界,再配合 BFS 向网格内部扩散,完整解释见图论笔记。
7. 84. 柱状图中最大的矩形:弹出时确定左右边界
对于每根柱子,希望知道它作为矩形最低高度时,能够向左右延伸到哪里。当前柱子更矮时,栈顶较高柱子不能再向右延伸,此时就可以结算它的最大面积。
为了让所有柱子最终都能结算,在数组两端各加入一个高度为 0 的哨兵:
1 | 原数组:[2, 1, 5, 6, 2, 3] |
1 | def largest_rectangle_area(heights: list[int]) -> int: |
下面用 heights = [2, 1, 5, 6, 2, 3] 演示。图中保留两端高度为 0 的哨兵;每当矮柱 right 迫使高柱 middle 出栈时,就用真实矩形覆盖它能够延伸的宽度,并计算候选面积。
extended = [0, 2, 1, 5, 6, 2, 3, 0]
current_height = extended[right]
while extended[stack[-1]] >= current_height
middle = stack.pop(); left = stack[-1]
width = right - left - 1
area = extended[middle] * width; best = max(best, area)
stack.append(right)
弹出 middle 时:
1 | right:右侧第一个阻止 middle 继续延伸的位置 |
使用 >= 会把相同高度的旧下标弹出,让更新的下标作为这一高度的新代表。len(stack) > 1 用来保护最左侧的 0 哨兵不被弹出。
左右哨兵分别解决两个边界问题:
- 左侧 0 保证弹出真实柱子后仍然有左边界。
- 右侧 0 强制栈中剩余柱子全部完成结算。
8. 接雨水和柱状图为什么看起来相反
这两题都使用 right - left - 1,但弹出的对象和面积含义不同:
| 对比 | 接雨水 | 最大矩形 |
|---|---|---|
| 栈内趋势 | 柱高非递增 | 柱高递增 |
| 当前元素触发条件 | 当前柱更高 | 当前柱更矮或相等 |
| 弹出的元素 | 凹槽底部 | 待结算的矩形高度 |
| 左右边界用途 | 两侧挡板 | 第一个限制延伸的位置 |
| 面积 | 宽度 * 水层高度 |
宽度 * 柱子高度 |
| 核心视角 | 横向一层层接水 | 以每根柱子为最低高度向两侧扩展 |
可以这样记:
1 | 接雨水:高柱出现,凹槽闭合 |
9. 从“下一个元素”推广到左右边界
单调栈不仅能直接返回下一个更大元素,还经常用来同时确定左右边界。
当当前下标使栈顶 middle 出栈时:
1 | 当前下标 current 通常是 middle 的右边界 |
这正是柱状图最大矩形的来源。类似地,在“子数组最小值之和”中,可以计算每个元素作为最小值时,向左和向右能够覆盖多少个子数组,再把贡献累加。
使用这种贡献法时,重复元素必须一侧严格、一侧非严格,例如:
1 | 左边找严格更小 |
如果两侧都使用严格关系,相同元素覆盖的子数组可能被重复统计;如果两侧都使用非严格关系,又可能漏掉一部分。具体选择哪一侧严格并不唯一,但两侧必须配套。
10. 常见错误
10.1 把当前下标和待结算下标写反
答案通常属于被弹出的旧下标:
1 | waiting = stack.pop() |
当前元素只是触发结算,不一定是在计算自己的答案。
10.2 栈里存下标,却直接比较下标大小
如果栈保存的是下标,比较时要回到原数组:
1 | nums[stack[-1]] < nums[current] |
不要误写成:
1 | stack[-1] < current |
后者比较的是位置,不是元素值。
10.3 没有单独决定相等元素的处理
< 与 <=、> 与 >= 会改变边界定义。每日温度要求严格更暖,相等温度不能出栈;贡献计数题又经常需要一侧处理相等值。
10.4 忘记处理永远等不到答案的元素
遍历结束后栈可能不为空。应该在初始化时给这些位置放好默认答案:
1 | 每日温度:0 |
10.5 看到两层循环就误判为 O(n²)
检查每个下标能否被重复压栈。如果每个下标只入栈、出栈一次,总复杂度仍然是 O(n)。
10.6 环形数组第二遍重复入栈
第二遍扫描只用于补齐第一遍元素的答案,通常只在第一遍执行 stack.append(current)。
11. 一份实用的单调栈检查清单
- 题目是否在问某一侧第一个更大或更小元素?
- 栈中保存的是仍在等待答案的谁?
- 当前元素在什么条件下能够结算栈顶?
- 栈保存下标还是数值?是否需要距离和边界?
- 相等元素应该保留还是弹出?
- 答案属于当前元素还是被弹出的元素?
- 弹出以后是否需要读取新的栈顶作为左边界?
- 找不到答案时的默认值是什么?
- 环形数组是否只在第一遍入栈?
- 是否需要左右哨兵强制完成边界结算?
12. 复习总览
- 单调栈解决“对每个元素寻找一侧第一个更大或更小元素”,把暴力扫描从
O(n^2)降为O(n)。 - 栈中通常保存下标,以便同时读取数值、计算距离并确定左右边界。
- 寻找右侧严格更大元素时,过去较小的元素等待在栈中;更大的当前元素到来后批量结算它们。
- 严格与非严格关系决定相等元素是否出栈,必须直接检查
while条件。 - 每日温度返回下标差;下一个更大元素返回对应数值;环形数组通过扫描两遍和取模补齐答案。
- 接雨水弹出凹槽底部,用左右挡板计算横向水层。
- 柱状图最大矩形弹出待结算高度,用左右限制位置计算矩形宽度。
- 接雨水遇到更高柱结算凹槽;柱状图遇到更矮柱结算矩形。
- 两端哨兵可以统一边界并强制栈内剩余元素完成结算。
- 单调栈中的
while虽然嵌套在for内,但每个下标只入栈、出栈一次,总时间仍然是O(n)。
复习单调栈时不要先背“递增栈还是递减栈”,先说清楚:谁在等待什么答案、当前元素为什么能让谁出栈、相等时要不要弹出。三个问题确定以后,栈的方向会自然得到。





