学习顺序主线第 11 / 22 课 · 阶段 4

为什么现在学:在栈的基础上维护候选,省掉反复向右扫描的工作。

返回算法课程
栈与队列进阶

单调栈Monotonic Stack

让还没找到答案的元素有序等待,新元素到来时批量解决问题。

40 分钟前置:栈 · 数组

学完这一课,你应该能做到

  • 说清栈中保存的是待回答的下标
  • 解释新元素为何同时解决多个旧元素
  • 区分下一个更大值与距离

01先从一个问题出发

对每天的温度,寻找右边第一次更热的那天。

一个具体的例子

[2,1,4,3];栈显示 下标:值,右端为栈顶。

把还没得到答案的元素留下来

对每个元素求右侧第一个严格更大的值。暴力方法从每个位置重新向右扫描,最坏 O(n²)。换一个视角:按从左到右的顺序接收新元素,让它回答之前尚未解决的请求。

看到 2,再看到 1,两者都还没有更大值,可以压入下标。现在 4 到来,比栈顶的 1 大,先解决 1;弹出后又比 2 大,再解决 2。一个新值完成了多个请求,而不是让多个起点各自扫描到它。

单调性保证只检查栈顶就够了

本课维护从栈底到栈顶数值非递增的下标栈。若新值不大于栈顶,也不可能大于下面更大的值,无需继续检查;若新值大于栈顶,就先解决并弹出它,直到栈顶不再更小。

保存下标而不是只保存数值,才能知道把答案写回哪个位置,也能计算间隔 i−previous。比如每日温度问的是等几天,不是返回那个更热的温度;核心维护不变,写答案的表达式会改变。

02最直接的办法,为什么慢?

对每个元素向右扫描,直到遇到更大值。

暴力 · O(n²)

许多位置会重复扫描同一片右侧区域。

03一步步,推导出优化思路

1

让未得到答案的下标等待

把未找到下一个更大值的位置存在栈里。

2

用单调关系整理候选

新值更大时不断弹栈,被弹出者第一次遇到更大值,答案确定。

3

新值到来,连续解决旧请求

新位置入栈,栈中对应值保持单调不增。

贯穿算法的不变量

栈中下标递增,对应值单调不增;它们尚未遇到右侧更大值。

拿一个小输入,逐步手算

[2,1,4,3];栈显示 下标:值,右端为栈顶。

当前 i / 值动作栈答案数组
0 / 2压入 0[0:2][−1,−1,−1,−1]
1 / 1压入 1[0:2,1:1]不变
2 / 4弹出 1,答案为 4[0:2][−1,4,−1,−1]
2 / 4弹出 0,答案为 4[][4,4,−1,−1]
2 / 4压入 2[2:4]不变
3 / 3压入 3[2:4,3:3]最终 [4,4,−1,−1]

最后仍在栈中的下标没有右侧更大值,保留默认 −1。这里 −1 是结果的约定标记;若输入也可为 −1,调用者需理解它可能与合法数值同形。

为什么找到的是第一个更大值

  1. 栈中每个下标都还没在已扫描范围内遇到更大值,否则早已弹出;栈中数值按非递增排列。
  2. 当前值大于栈顶时,它确实在该下标右侧;又因此前扫描没有更大值,所以当前就是第一个符合条件的位置。
  3. 连续弹出所有更小值再压入当前下标,单调性恢复。扫描结束后留下的请求确实无解。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Monotonic Stack交互演示
STEP 01 / 14
2
0
1
1
4
2
3
3
当前处理已处理 / 已确定未处理
01

栈存索引。栈底到栈顶对应的值保持单调不增。

monotonic_stack.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

stack, answer = [], [-1] * len(a)
answer 的每项默认无解,stack 仅保存未解决的下标。这里复制整数 −1 没有共享可变对象的问题。
while stack and a[stack[-1]] < value:
先检查栈非空,再通过下标取值比较。题目要严格更大,因此相等不能弹出。
answer[previous] = value
本实现返回更大值。若问等待距离,应写 i−previous;若问位置,应写 i。
stack.append(i)
当前下标也要等待它右侧的答案,解决旧请求后再压入。

05复杂度,来自具体的工作量

时间复杂度
O(n)O(n)

每个下标入栈一次,最多出栈一次,累计 O(n),不是按嵌套循环直接判平方。

辅助空间
O(n)O(n)

最坏递减输入下全部下标留在栈中;答案数组也有 n 个元素。

拖动 n,看看增长速度

把工作量具体数出来

每个下标只入栈一次,也最多出栈一次,总栈操作≤2n,所以时间 O(n)。这是对整个运行过程计数,而不是把某一轮多次弹出乘上 n。

单调递减输入会让栈存下全部 n 个下标,因此辅助空间 O(n)。结果数组也占 O(n)。

相等值在此实现里可以同时留在栈中;若题目改为大于等于,比较符号和不变量都要相应改写。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

栈里存下标

用下标才能把答案写回原位置,重复值也能区分。

02

严格与非严格

题目要更大值时用 < 弹栈;相等值不是答案。

用反例检查前提

用 ≤ 会把相等值当成更大值

输入 [2,2,3],下标 0 的第一个严格更大值应该是 3。若相等也弹出,会在读第二个 2 时错误给出答案 2。

怎样修正:先读清题意的严格性,再决定 < 或 ≤。在注释中写出栈值应是严格递减还是非递增,并用重复值测试。

08把想法带进真实题目

合上答案,自己推一次

从数值答案迁移到距离答案

对温度 [70,68,72,71],求每个位置等几天才能更热,无解记 0。答案是什么,核心代码改哪里?

需要一点提示

72 同时解决 68 和 70,但距离不同。

查看完整推导与答案
  1. 答案为 [2,1,0,0]。70 在两天后等到 72,68 在一天后等到 72。
  2. 将默认答案设为 0,弹出 previous 时写入 i−previous。
  3. 栈中仍然保存下标,比较时仍然读取 a[stack[-1]];不能仅保存温度,否则丢失距离信息。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01为什么通常存下标?

02每个元素最多出栈几次?

03找严格更大值时,相等元素应弹出吗?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。