739. 每日温度
739. 每日温度
题目链接（中等）
题目描述
给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
数据范围：
1 <= temperatures.length <= 10^530 <= temperatures[i] <= 100
示例
示例 1：
输入： temperatures = [73,74,75,71,69,72,76,73]
输出： [1,1,4,2,1,1,0,0]
示例 2：
输入： temperatures = [30,40,50,60]
输出： [1,1,1,0]
示例 3：
输入： temperatures = [30,60,90]
输出： [1,1,0]
核心思路
问题本质：对每个位置 i，找右侧第一个比它大的元素的下标 j，answer[i] = j - i。没有则 answer[i] = 0。
这就是经典的 「下一个更大元素」 问题。
两种解法：
- 暴力 + 温度数组：因为温度范围小（30~100），用数组记录每个温度「最早出现的位置」，从右往左扫描；
- 单调栈（推荐）：维护一个「温度递减」的单调栈，遇到更大的温度就弹出栈顶并记录答案，时间 $O(n)$。
方法一：暴力 + 温度范围优化
思路及解法
观察：温度范围只有 [30, 100]，共 71 种可能。
用数组 nxt[t] 记录「温度 t 最早出现的下标」。
从右往左遍历温度列表：
- 对每个
temperatures[i]，在nxt[t]中找t ∈ [temperatures[i]+1, 100]的最小下标warmer_index； - 若
warmer_index存在，ans[i] = warmer_index - i； - 更新
nxt[temperatures[i]] = i。
为什么从右往左：
- 遍历到
i时，nxt里存的都是i右侧的信息； - 从右往左保证「已经访问过的」都是右侧的。
代码
class Solution:
def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
n = len(temperatures)
ans = [0] * n
nxt = {} # 每个温度最早出现的下标
big = float('inf')
for i in range(n - 1, -1, -1):
# 找比当前温度高的、最早出现的下标
warmer_index = min(
(nxt[t] for t in range(temperatures[i] + 1, 101) if t in nxt),
default=big,
)
if warmer_index != big:
ans[i] = warmer_index - i
nxt[temperatures[i]] = i
return ans复杂度分析
- 时间复杂度：$O(n \cdot m)$，其中 $m = 71$ 是温度范围。
- 空间复杂度：$O(m)$。
方法二：单调栈（推荐）
思路及解法
维护一个单调栈，栈里存下标，从栈底到栈顶对应温度递减。
关键点：栈里的下标都表示「还没找到下一个更高温度」的天。
遍历过程（从左到右）：
- 对于当前温度
temperatures[i]：- 当栈非空，且
temperatures[i] > temperatures[stack[-1]]时，说明栈顶那天找到了它的「下一个更高温度」； - 弹出栈顶
prev_index，ans[prev_index] = i - prev_index； - 重复直到不满足条件为止；
- 当栈非空，且
- 把
i入栈。
为什么可以在弹栈时确定答案：
- 如果栈顶
prev_index和i之间有比temperatures[i]大的元素，那么prev_index会在那一步被弹出； - 所以当
i使得栈顶被弹出时，temperatures[i]一定是temperatures[prev_index]右侧的第一个更大值。
为什么栈内温度递减：
- 每次有更大的温度入栈，比它小的都会被弹掉；
- 因此栈内始终保持递减。
举例：temperatures = [73,74,75,71,69,72,76,73]
| i | 温度 | 弹栈操作 | ans | 栈（下标(温度)） |
|---|---|---|---|---|
| 0 | 73 | — | [0,...] |
[0(73)] |
| 1 | 74 | 弹 0 | [1,0,...] |
[1(74)] |
| 2 | 75 | 弹 1 | [1,1,0,...] |
[2(75)] |
| 3 | 71 | — | [1,1,0,...] |
[2(75),3(71)] |
| 4 | 69 | — | [1,1,0,...] |
[2(75),3(71),4(69)] |
| 5 | 72 | 弹 4、3 | [1,1,0,2,1,0,...] |
[2(75),5(72)] |
| 6 | 76 | 弹 5、2 | [1,1,4,2,1,1,0,0] |
[6(76)] |
| 7 | 73 | — | [1,1,4,2,1,1,0,0] |
[6(76),7(73)] |
最终结果 [1,1,4,2,1,1,0,0]，正确。
代码
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
n = len(temperatures)
answer = [0] * n
stack = [] # 存下标，对应温度单调递减
for i, t in enumerate(temperatures):
while stack and t > temperatures[stack[-1]]:
prev = stack.pop()
answer[prev] = i - prev
stack.append(i)
return answer复杂度分析
- 时间复杂度：$O(n)$，每个下标最多入栈、出栈一次。
- 空间复杂度：$O(n)$，栈最多存
n个下标。
两种方法对比
| 方法 | 时间 | 空间 | 特点 |
|---|---|---|---|
| 暴力 + 温度数组 | $O(n \cdot m)$ | $O(m)$ | 利用温度范围小，思路略绕 |
| 单调栈 | $O(n)$ | $O(n)$ | 通用模板，面试首选 |
推荐：
- 面试：直接写单调栈，是「下一个更大元素」问题的通用模板，可以迁移到很多题；
- 温度范围小的场景：方法一也能过，但通用性差。
关键细节
1. 为什么栈里存下标而不是值
因为答案需要「下标差」（i - prev_index），存下标方便计算。同时也可以通过 temperatures[stack[-1]] 访问对应的温度。
2. 「下一个更大元素」的模板
stack = []
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]]:
prev_index = stack.pop()
ans[prev_index] = i - prev_index
stack.append(i)这个模板可以处理：
- 下一个更大元素（本题、LC 496、LC 503）；
- 下一个更小元素（把
>改成<）； - 每日温度（本题）；
- 接雨水（换成另一种用法）；
- 柱状图中最大矩形（单调栈基础）。
3. 为什么从栈底到栈顶递减
- 每次新元素入栈前，比它小的都会被弹掉；
- 所以栈内元素对应的温度始终递减；
- 递减的栈保证了「栈顶是最近的、还没被超越的候选」。
4. 单调栈的两种写法
写法一（本题）：遍历时弹栈并更新答案。
while stack and temperatures[i] > temperatures[stack[-1]]:
...写法二：某些题需要保留相等元素或处理其他逻辑，可根据需求调整比较条件。
5. 与暴力法的对比
暴力法每个位置都要向右扫，最坏 $O(n^2)$。单调栈利用「栈内元素都还没有找到答案」这个性质，把重复扫描降到 $O(n)$。
6. 与 LC 496（下一个更大元素 I）的关系
LC 496 是本题的简化版（在 nums2 中找 nums1 每个元素的下一个更大元素），核心也是单调栈。本题相当于在每个位置都要找。
总结
- 核心问题：对每个位置，找右侧第一个更大的元素下标差；
- 单调栈：
- 栈里存下标，栈内温度递减；
- 遍历到
i时，若temperatures[i]比栈顶大，弹出并记录答案； - 最后把
i入栈； - 时间 $O(n)$、空间 $O(n)$；
- 暴力法：利用温度范围小（30~100），从右往左扫描，时间 $O(n \cdot 71)$；
- 通用套路：「下一个更大 / 更小元素」→ 单调栈。
相关题目
- LC 496. 下一个更大元素 I（单调栈入门）
- LC 503. 下一个更大元素 II（循环数组，单调栈）
- LC 42. 接雨水（单调栈 + 计算面积）
- LC 84. 柱状图中最大的矩形（单调栈进阶）
- LC 901. 股票价格跨度（单调栈设计题）