01先从一个问题出发
对每天的温度,寻找右边第一次更热的那天。
[2,1,4,3];栈显示 下标:值,右端为栈顶。
把还没得到答案的元素留下来
对每个元素求右侧第一个严格更大的值。暴力方法从每个位置重新向右扫描,最坏 O(n²)。换一个视角:按从左到右的顺序接收新元素,让它回答之前尚未解决的请求。
看到 2,再看到 1,两者都还没有更大值,可以压入下标。现在 4 到来,比栈顶的 1 大,先解决 1;弹出后又比 2 大,再解决 2。一个新值完成了多个请求,而不是让多个起点各自扫描到它。
单调性保证只检查栈顶就够了
本课维护从栈底到栈顶数值非递增的下标栈。若新值不大于栈顶,也不可能大于下面更大的值,无需继续检查;若新值大于栈顶,就先解决并弹出它,直到栈顶不再更小。
保存下标而不是只保存数值,才能知道把答案写回哪个位置,也能计算间隔 i−previous。比如每日温度问的是等几天,不是返回那个更热的温度;核心维护不变,写答案的表达式会改变。
02最直接的办法,为什么慢?
对每个元素向右扫描,直到遇到更大值。
许多位置会重复扫描同一片右侧区域。
03一步步,推导出优化思路
让未得到答案的下标等待
把未找到下一个更大值的位置存在栈里。
用单调关系整理候选
新值更大时不断弹栈,被弹出者第一次遇到更大值,答案确定。
新值到来,连续解决旧请求
新位置入栈,栈中对应值保持单调不增。
栈中下标递增,对应值单调不增;它们尚未遇到右侧更大值。
拿一个小输入,逐步手算
[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,调用者需理解它可能与合法数值同形。
为什么找到的是第一个更大值
- 栈中每个下标都还没在已扫描范围内遇到更大值,否则早已弹出;栈中数值按非递增排列。
- 当前值大于栈顶时,它确实在该下标右侧;又因此前扫描没有更大值,所以当前就是第一个符合条件的位置。
- 连续弹出所有更小值再压入当前下标,单调性恢复。扫描结束后留下的请求确实无解。
04让每一步,都看得见
试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。
栈存索引。栈底到栈顶对应的值保持单调不增。
动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。
代码里的每个关键决定
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),不是按嵌套循环直接判平方。
最坏递减输入下全部下标留在栈中;答案数组也有 n 个元素。
把工作量具体数出来
每个下标只入栈一次,也最多出栈一次,总栈操作≤2n,所以时间 O(n)。这是对整个运行过程计数,而不是把某一轮多次弹出乘上 n。
单调递减输入会让栈存下全部 n 个下标,因此辅助空间 O(n)。结果数组也占 O(n)。
相等值在此实现里可以同时留在栈中;若题目改为大于等于,比较符号和不变量都要相应改写。
06看到什么,应该想到它?
关键词只是线索,继续检查适用条件07这些细节,容易踩坑
栈里存下标
用下标才能把答案写回原位置,重复值也能区分。
严格与非严格
题目要更大值时用 < 弹栈;相等值不是答案。
用 ≤ 会把相等值当成更大值
输入 [2,2,3],下标 0 的第一个严格更大值应该是 3。若相等也弹出,会在读第二个 2 时错误给出答案 2。
怎样修正:先读清题意的严格性,再决定 < 或 ≤。在注释中写出栈值应是严格递减还是非递增,并用重复值测试。
08把想法带进真实题目
从数值答案迁移到距离答案
对温度 [70,68,72,71],求每个位置等几天才能更热,无解记 0。答案是什么,核心代码改哪里?
需要一点提示
72 同时解决 68 和 70,但距离不同。
查看完整推导与答案
- 答案为 [2,1,0,0]。70 在两天后等到 72,68 在一天后等到 72。
- 将默认答案设为 0,弹出 previous 时写入 i−previous。
- 栈中仍然保存下标,比较时仍然读取 a[stack[-1]];不能仅保存温度,否则丢失距离信息。
完成上面的手算练习,再把思路迁移到这些题目。
09不用背模板,回答这几个问题
01为什么通常存下标?
02每个元素最多出栈几次?
03找严格更大值时,相等元素应弹出吗?
你已经走完了这次推导。
能用自己的话解释复杂度和不变量,再标记为掌握。