第3章｜栈与队列
Unit 08 · 当前元素批量解决历史问题
← Unit 07
U08
Daily TemperaturesIndex Stack · Distance · Resolve
当前温度不只描述今天，
还会一次解决多个等待中的过去。
普通“下一个更大元素”只需要记录更大的值；本题还要回答等待了几天，因此单调栈必须保存日期索引。某个历史日期出栈时，当前索引与它的差值就是最终答案。
LeetCode #739 题目模型返回等待天数，而不是更高温度本身
题目要求
给定整数数组 temperatures，其中 temperatures[i] 表示第 i 天温度。返回数组 answer：answer[i] 表示从第 i 天起，需要等待多少天才会出现更高温度；若之后没有更高温度，则为 0。
from typing import List
class Solution:
def dailyTemperatures(
self,
temperatures: List[int]
) -> List[int]:
pass
输入、输出与复杂度目标
- 输入：每日温度数组；输出：等长等待天数数组；
- 建议时间复杂度：
O(n)； - 额外空间复杂度：
O(n)。
示例
输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]
输出：[1,1,4,2,1,1,0,0]
输入：[30,40,50,60]
输出：[1,1,1,0]
输出：[1,1,1,0]
输入：[30,60,90]
输出：[1,1,0]
输出：[1,1,0]
数据约束
1 ≤ temperatures.length ≤ 10⁵30 ≤ temperatures[i] ≤ 100- 只有严格更高温度才能结束等待；相同温度不算。
Pending Day
已扫描但尚未遇到更高温度的日期。它们进入栈，继续等待未来信息。
Index Stack
栈保存索引而非温度，既能比较温度，也能计算等待天数。
Monotonicity
栈中索引对应温度从栈底到栈顶单调不增。
Resolve on Pop
历史日期被弹出时，当前日是它右侧第一个更暖日期，答案立即确定。
Unit 07 → Unit 08：从“答案是什么”迁移到“答案距离多远”保存对象的语义升级
#496 下一个更大元素
弹栈时只需记录“更大值是什么”。元素互不相同时，可以用值建立映射。
→
#739 每日温度
弹栈时还要计算等待天数，因此必须保存日期索引；索引同时决定答案写入位置和距离。
认知任务 1
第 2 天温度 75，需要等待多少天才会更暖？
从当前日期向右寻找第一个严格更高温度；答案是索引距离，不是温度差。
主动画区人工扫描模式
temperatures = [73,74,75,71,69,72,76,73]当前目标：第 2 天，75°C
未解决日期栈 保存 index，不保存裸温度
answer 数组 出栈时写入 index 差
answer[past] = current_index - past
准备从第 2 天向右扫描。
比较次数0
入栈次数0
出栈次数0
已确定答案0
累计工作量
Read
Compare Top
Pop Index
Write Distance
Push Index
Finish
关键代码补全
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer =
stack = []
for index, temperature in enumerate(temperatures):
while stack and :
previous_index = stack.pop()
answer[previous_index] =
stack.append()
return answer
from typing import List
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack = []
for index, temperature in enumerate(temperatures):
while stack and temperature > temperatures[stack[-1]]:
previous_index = stack.pop()
answer[previous_index] = index - previous_index
stack.append(index)
return answer
时间复杂度：O(n)。每个索引最多入栈一次、出栈一次。
空间复杂度：O(n)。答案数组之外，单调栈最坏保存 n 个索引。
代码与图像逐行联动
1from typing import List
3class Solution:
4 def dailyTemperatures(...):
5 n = len(temperatures)
6 answer = [0] * n
7 stack = []
9 for index, temperature in enumerate(temperatures):
10 while stack and temperature > temperatures[stack[-1]]:
11 previous_index = stack.pop()
12 answer[previous_index] = index - previous_index
13 stack.append(index)
15 return answer
index / temperature—
stack indices[]
stack temps[]
previous_index—
answer[]
判断 / 返回—
进入函数，准备初始化答案数组和索引栈。
完成代码联动后进入 LeetCode #901 股票价格跨度迁移代码正确、查看参考答案、一键填入或播放完整轨迹后解锁。
迁移题：LeetCode #901「股票价格跨度」
从离线数组转向在线数据流：每次调用 next(price) 都要立即返回今天向左连续、不高于今天价格的天数。
1 认识官方原题
2 对照 #739 / #901
3 映射四个状态变化
4 运行官方样例
第一步：先读懂 #901，而不是直接套用单调栈模板
官方题目要求
设计一个接收每日股票价格的数据结构。对今天的价格 price，返回一个跨度：从今天向过去连续计算，价格小于或等于今天价格的最大连续天数。
class StockSpanner:
def __init__(self):
...
def next(self, price: int) -> int:
...
约束
1 ≤ price ≤ 10⁵- 最多调用
next共10⁴次
官方示例
输入调用：
["StockSpanner","next","next","next","next","next","next","next"]
[[],[100],[80],[60],[70],[60],[75],[85]]
输出：
[null,1,1,1,2,1,4,6]
例如价格 75 到来时，向左连续的 60、70、60 都不高于 75，再加上今天，共 4 天。
在线数据流
不能预先遍历完整数组；一次只接收今天的价格。
包含今天
即使昨天更高，今天自己的跨度也至少为 1。
小于或等于
相等价格也属于今天能够覆盖的连续区间。
立即返回
每次 next 只返回今天的一个整数，而非最终数组。
读题检查 1：依次输入 100、80、60、70，next(70) 返回多少？
从今天向左，遇到第一个严格大于今天价格的日期就停止。
读题检查 2：连续两天价格都是 100，第二天跨度是多少？
题面使用的是“less than or equal to”。
完成两道读题检查后解锁结构对照
第二步：#739 与 #901 复用同一个“弹栈归约”机制，但答案方向相反
#739 每日温度
输入形态一次拿到完整数组，离线处理
提问方向等待未来第一个严格更高温度
栈元素历史日期索引
弹栈结果给过去日期写入未来距离
比较条件
current > stack_top#901 股票价格跨度
输入形态价格逐日到来，在线回答
提问方向统计今天向左连续不高于今天的天数
栈元素
(price, compressed_span)弹栈结果把历史跨度合并到今天
比较条件
stack_top_price <= current关键迁移：#739 弹栈时把答案写给“过去”；#901 弹栈时把过去已经压缩好的跨度累加给“今天”。因此 #901 不需要保存所有日期索引，而要让每个栈项携带一段已经计算完成的连续区间。
#901 为什么不能把栈项只写成价格？
回答结构问题后解锁语义槽位
第三步：把 #739 的索引栈逐项迁移为在线跨度栈
槽位 1 · 栈项保存什么？
今天需要复用历史已经计算出的连续区间。
槽位 2 · 今天的基础跨度
跨度必须包含今天自身。
槽位 3 · 哪些历史组可以被合并？
相等价格同样属于“不高于今天”。
槽位 4 · 如何保存并返回今天？
今天的价格与压缩跨度成为未来的一个整体。
拼装结果：黄色行是从 #739 迁移后发生语义变化的位置
完成四个槽位后生成 StockSpanner 脚手架。
- stack 保存未解决日期索引
+ stack 保存 (price, compressed_span)
- current_temp > previous_temp
+ previous_price <= current_price
- answer[past] = current_index - past
+ current_span += popped_span
- 扫描结束统一返回 answer 数组
+ 每次 next(price) 立即返回今天的 span
完成四个槽位后解锁官方样例
第四步：逐次调用官方样例，观察跨度如何被压缩和复用
当前调用StockSpanner()
今天初始 span—
本次合并—
返回值null
初始化空的单调递减价格栈。
累计输出：[null]
可选挑战：不复制参考答案，独立重写完整类
Unit 08 Skill 卡
单调栈不仅能寻找未来边界，也能压缩过去连续区间。#739 保存索引，在未来事件到来时给过去写距离；#901 保存 (price, span)，在今天到来时把被支配的历史区间合并到今天。
主问题#739 · 右侧更高温度距离
迁移问题#901 · 在线股票跨度
核心表示索引栈 → (price, span) 压缩栈
比较边界#739 使用 >；#901 使用 <=
答案流向给过去写答案 → 给今天累计答案
复杂度每个价格组至多入栈、出栈一次，均摊 O(1)
常见错误忘记包含今天；相等价格不合并；只保存价格
下一迁移#84 柱状图边界与面积
抽象能力识别“弹栈时答案属于过去还是当前”