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
2
3
每个下标入栈最多 1 次
每个下标出栈最多 1 次
总操作次数不超过常数倍 n

因此一次完整扫描的时间复杂度是 O(n),栈的空间复杂度是 O(n)。这叫摊还分析,不是把内外循环简单相乘成 O(n^2)。

3. 一套统一的“下一个严格更大”模板

先写一个返回下标的通用版本:

1
2
3
4
5
6
7
8
9
10
11
12
def next_strictly_greater_indices(nums: list[int]) -> list[int]:
answer = [-1] * len(nums)
stack: list[int] = []

for current in range(len(nums)):
while stack and nums[stack[-1]] < nums[current]:
waiting = stack.pop()
answer[waiting] = current

stack.append(current)

return answer

下面用 nums = [2, 1, 2, 4, 3] 把模板逐句展开。这个例子特意放了两个相等的 2:当当前值也是 2 时,2 < 2 为假,所以旧的 2 仍要留在栈中;直到 4 到来,它们才依次找到答案。

下一个严格更大:等待者怎样被当前元素结算 nums = [2, 1, 2, 4, 3]
动作: 当前: 判断:
for current in range(len(nums)) while stack and nums[stack[-1]] < nums[current] waiting = stack.pop(); answer[waiting] = current stack.append(current)
stack:栈底 → 栈顶
answer:保存下一个严格更大元素的下标

理解模板时只看两个角色:

1
2
waiting:过去出现、仍在等待答案的下标
current:当前到来、可能解决若干 waiting 的下标

从这个模板可以直接改出不同返回形式:

1
2
3
返回更大元素的下标:answer[waiting] = current
返回更大元素的数值:answer[waiting] = nums[current]
返回还要等待的距离:answer[waiting] = current - waiting

遍历结束后仍留在栈中的位置,说明右侧不存在符合条件的元素,因此保留初始化答案,例如 -1 或 0。

写题前先回答四个问题:

  1. 栈里保存下标还是数值?
  2. 谁在等待答案,谁触发结算?
  3. 要找严格更大、更大等于、严格更小,还是更小等于?
  4. 找不到答案时应该返回 -1、0 还是数组边界?

4. 739. 每日温度:单调栈入门题

题目要求每一天距离右侧第一个更高温度还有几天,因此:

1
2
3
栈中保存仍未找到更暖日期的下标
当前温度更高时,批量结算栈顶日期
答案是两个下标之差
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def daily_temperatures(temperatures: list[int]) -> list[int]:
answer = [0] * len(temperatures)
stack: list[int] = []

for current, temperature in enumerate(temperatures):
while (
stack
and temperatures[stack[-1]] < temperature
):
waiting = stack.pop()
answer[waiting] = current - waiting

stack.append(current)

return answer

以 [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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def next_greater_element(
nums1: list[int],
nums2: list[int],
) -> list[int]:
next_greater: dict[int, int] = {}
stack: list[int] = []

for current in nums2:
while stack and stack[-1] < current:
waiting = stack.pop()
next_greater[waiting] = current

stack.append(current)

return [
next_greater.get(value, -1)
for value in nums1
]

这里可以直接保存数值,是因为题目保证 nums2 中所有整数互不相同。如果允许重复值,value -> answer 无法区分不同位置,应该改成保存下标。

5.2 503. 下一个更大元素 II:用取模模拟环形数组

环形数组中,末尾元素还可以继续查看数组开头。把下标范围扫描两遍,就相当于把数组复制了一份:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def next_greater_elements(nums: list[int]) -> list[int]:
size = len(nums)
answer = [-1] * size
stack: list[int] = []

for step in range(2 * size):
current = step % size

while (
stack
and nums[stack[-1]] < nums[current]
):
waiting = stack.pop()
answer[waiting] = nums[current]

# 第二遍只负责帮助第一遍的下标找到答案。
if step < size:
stack.append(current)

return answer

第二遍不要再次把下标入栈,否则同一个位置会重复等待答案,既增加无效操作,也让状态难以解释。

取模只是模拟访问顺序:

1
2
step:0, 1, ..., n-1, n, ..., 2n-1
下标:0, 1, ..., n-1, 0, ..., n-1

6. 42. 接雨水:弹出的是凹槽底部

接雨水使用单调栈时,栈中保存尚未找到右侧挡板的柱子下标。当前柱子比栈顶更高,说明出现了右挡板,可以按水平方向计算一层积水。

弹出一个凹槽底部 bottom 后:

1
2
3
4
5
right = 当前下标
left = 弹出 bottom 后的新栈顶
宽度 = right - left - 1
有效水位 = min(height[left], height[right])
积水高度 = 有效水位 - height[bottom]
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
def trap(height: list[int]) -> int:
water = 0
stack: list[int] = []

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]
width = right - left - 1
bounded_height = (
min(height[left], right_height)
- height[bottom]
)
water += width * bounded_height

stack.append(right)

return water

下面用 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)
stack(栈底 → 栈顶)

这里最容易错的地方:

  1. bottom 弹出以后,新的栈顶才是左挡板。
  2. 弹出后栈为空,说明没有左挡板,必须停止当前轮计算。
  3. 宽度不包含左右挡板,所以是 right - left - 1。
  4. 水位由较矮挡板决定,所以使用 min(left_height, right_height)。
  5. 一次弹出计算的是一层横向积水,不是某一根柱子上方的全部水量。

二维扩展题 407. 接雨水 II 不能再只看左右两根挡板:水可能从上下左右任意方向流走。它需要用小根堆维护整圈最低边界,再配合 BFS 向网格内部扩散,完整解释见图论笔记。

7. 84. 柱状图中最大的矩形:弹出时确定左右边界

对于每根柱子,希望知道它作为矩形最低高度时,能够向左右延伸到哪里。当前柱子更矮时,栈顶较高柱子不能再向右延伸,此时就可以结算它的最大面积。

为了让所有柱子最终都能结算,在数组两端各加入一个高度为 0 的哨兵:

1
2
原数组:[2, 1, 5, 6, 2, 3]
扩展后:[0, 2, 1, 5, 6, 2, 3, 0]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def largest_rectangle_area(heights: list[int]) -> int:
extended = [0, *heights, 0]
stack = [0]
best = 0

for right in range(1, len(extended)):
current_height = extended[right]

while (
len(stack) > 1
and 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)

return best

下面用 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)
stack(栈底 → 栈顶)

弹出 middle 时:

1
2
3
4
right:右侧第一个阻止 middle 继续延伸的位置
left:弹出 middle 后,栈中最近的更矮位置
可用宽度:right - left - 1
矩形高度:height[middle]

使用 >= 会把相同高度的旧下标弹出,让更新的下标作为这一高度的新代表。len(stack) > 1 用来保护最左侧的 0 哨兵不被弹出。

左右哨兵分别解决两个边界问题:

  • 左侧 0 保证弹出真实柱子后仍然有左边界。
  • 右侧 0 强制栈中剩余柱子全部完成结算。

8. 接雨水和柱状图为什么看起来相反

这两题都使用 right - left - 1,但弹出的对象和面积含义不同:

对比 接雨水 最大矩形
栈内趋势 柱高非递增 柱高递增
当前元素触发条件 当前柱更高 当前柱更矮或相等
弹出的元素 凹槽底部 待结算的矩形高度
左右边界用途 两侧挡板 第一个限制延伸的位置
面积 宽度 * 水层高度 宽度 * 柱子高度
核心视角 横向一层层接水 以每根柱子为最低高度向两侧扩展

可以这样记:

1
2
接雨水:高柱出现,凹槽闭合
柱状图:矮柱出现,高矩形闭合

9. 从“下一个元素”推广到左右边界

单调栈不仅能直接返回下一个更大元素,还经常用来同时确定左右边界。

当当前下标使栈顶 middle 出栈时:

1
2
当前下标 current 通常是 middle 的右边界
弹出后的新栈顶通常是 middle 的左边界

这正是柱状图最大矩形的来源。类似地,在“子数组最小值之和”中,可以计算每个元素作为最小值时,向左和向右能够覆盖多少个子数组,再把贡献累加。

使用这种贡献法时,重复元素必须一侧严格、一侧非严格,例如:

1
2
左边找严格更小
右边找小于等于

如果两侧都使用严格关系,相同元素覆盖的子数组可能被重复统计;如果两侧都使用非严格关系,又可能漏掉一部分。具体选择哪一侧严格并不唯一,但两侧必须配套。

10. 常见错误

10.1 把当前下标和待结算下标写反

答案通常属于被弹出的旧下标:

1
2
waiting = stack.pop()
answer[waiting] = current - waiting

当前元素只是触发结算,不一定是在计算自己的答案。

10.2 栈里存下标,却直接比较下标大小

如果栈保存的是下标,比较时要回到原数组:

1
nums[stack[-1]] < nums[current]

不要误写成:

1
stack[-1] < current

后者比较的是位置,不是元素值。

10.3 没有单独决定相等元素的处理

< 与 <=、> 与 >= 会改变边界定义。每日温度要求严格更暖,相等温度不能出栈;贡献计数题又经常需要一侧处理相等值。

10.4 忘记处理永远等不到答案的元素

遍历结束后栈可能不为空。应该在初始化时给这些位置放好默认答案:

1
2
3
每日温度:0
下一个更大元素:-1
左右边界:-1 或 n

10.5 看到两层循环就误判为 O(n²)

检查每个下标能否被重复压栈。如果每个下标只入栈、出栈一次,总复杂度仍然是 O(n)。

10.6 环形数组第二遍重复入栈

第二遍扫描只用于补齐第一遍元素的答案,通常只在第一遍执行 stack.append(current)。

11. 一份实用的单调栈检查清单

  1. 题目是否在问某一侧第一个更大或更小元素?
  2. 栈中保存的是仍在等待答案的谁?
  3. 当前元素在什么条件下能够结算栈顶?
  4. 栈保存下标还是数值?是否需要距离和边界?
  5. 相等元素应该保留还是弹出?
  6. 答案属于当前元素还是被弹出的元素?
  7. 弹出以后是否需要读取新的栈顶作为左边界?
  8. 找不到答案时的默认值是什么?
  9. 环形数组是否只在第一遍入栈?
  10. 是否需要左右哨兵强制完成边界结算?

12. 复习总览

  • 单调栈解决“对每个元素寻找一侧第一个更大或更小元素”,把暴力扫描从 O(n^2) 降为 O(n)。
  • 栈中通常保存下标,以便同时读取数值、计算距离并确定左右边界。
  • 寻找右侧严格更大元素时,过去较小的元素等待在栈中;更大的当前元素到来后批量结算它们。
  • 严格与非严格关系决定相等元素是否出栈,必须直接检查 while 条件。
  • 每日温度返回下标差;下一个更大元素返回对应数值;环形数组通过扫描两遍和取模补齐答案。
  • 接雨水弹出凹槽底部,用左右挡板计算横向水层。
  • 柱状图最大矩形弹出待结算高度,用左右限制位置计算矩形宽度。
  • 接雨水遇到更高柱结算凹槽;柱状图遇到更矮柱结算矩形。
  • 两端哨兵可以统一边界并强制栈内剩余元素完成结算。
  • 单调栈中的 while 虽然嵌套在 for 内,但每个下标只入栈、出栈一次,总时间仍然是 O(n)。

复习单调栈时不要先背“递增栈还是递减栈”,先说清楚:谁在等待什么答案、当前元素为什么能让谁出栈、相等时要不要弹出。三个问题确定以后,栈的方向会自然得到。

avatar
LittlePyx
小P的学习、研究、生活记录
Follow Me
公告
教育经历
本科:杭州电子科技大学
研究生:电子科技大学

研究方向
AI Agent 开发、计算成像、深度学习、光学

新增:代码随想录算法刷题笔记整理中,按题型与算法模板归纳。
最新文章
网站信息
文章数目 :
18
最后更新时间 :