LeetCode 739. 每日温度
目录
题目描述
题意分析
给定每天的温度数组，对每一天回答同一个问题：还要等几天才第一次出现比今天更高的温度。注意问的是「等几天」而不是「那天是多少度」，也就是两个下标之差；如果之后再也没有更暖的日子，该位置填 0。
「第一次」意味着每一天只关心它右侧最近的那个更高温度，后面更高的都无关；「更高」是严格大于，温度相等不算数。
约束信号：天数最多可到 $10^5$ 量级，对每一天向右暴力找的 $O(n^2)$ 做法在最坏输入下会超时；温度值有上下界，但答案只依赖相对大小和位置。边界上，最后一天必为 0，单调不升的整段（如一路降温）也全是 0。
解法：单调栈保存未匹配日期
核心思路
问题关键：每一天要找右侧第一个严格更高的温度。逐日向右扫描会重复比较，最坏是 $O(n^2)$；单调栈可以统一保存“还没找到答案”的日期。
栈中保存日期下标，并维护不变量：从栈底到栈顶，下标递增，对应温度非递增。保存下标是因为既要比较温度，又要用下标差计算等待天数；相等温度不能弹出，所以这里是“非递增”而不是“严格递减”。
遍历到第
i天时，只要当前温度高于栈顶日期，就弹出prev并记录i - prev。i一定是prev右侧第一个更暖日：若中间已有更暖日期，prev当时就会被弹出。最后仍在栈中的日期右侧没有更暖日，答案保持默认值0。
解题步骤
- 创建全为
0的答案数组和空栈，栈中保存日期下标。- 从左到右遍历下标
i；当前温度高于栈顶温度时，持续弹栈。- 每弹出一个下标
prev，写入answer[prev] = i - prev。- 弹栈结束后把
i入栈，等待未来更高的温度。- 遍历结束直接返回；栈中剩余日期没有答案，保持
0。例如
[73,74,75,71,69,72]：遇到72时会依次弹出69、71对应的下标，分别得到等待1、2天；75仍高于72，因此留在栈中。
代码实现
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] res = new int[temperatures.length];
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < temperatures.length; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prev = stack.pop();
// 当前日期是 prev 之后第一个更高温度日期。
res[prev] = i - prev;
}
stack.push(i);
}
return res;
}
}
func dailyTemperatures(temperatures []int) []int {
res := make([]int, len(temperatures))
stack := make([]int, 0)
for i := 0; i < len(temperatures); i++ {
for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
prev := stack[len(stack)-1]
stack = stack[:len(stack)-1]
// 当前下标为 prev 找到第一个更高温度。
res[prev] = i - prev
}
stack = append(stack, i)
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。虽然内层 while 看起来可能循环很多次，但每个下标恰好入栈一次、至多出栈一次，所有轮次的弹栈总量不超过 $n$，摊还到每天是常数——这正是单调栈从 $O(n^2)$ 降到线性的关键论证。
- 空间复杂度：$O(n)$。栈在最坏情况（温度单调不升，如一路降温）会保存全部下标；答案数组按惯例不计入额外空间。
关键点总结
- 栈保存尚未匹配的下标，出栈时同时得到温度和距离。
- 找右侧第一个更大元素，正向遍历并维护温度非递增栈。
- 相等温度不满足题意，弹栈条件必须是当前温度严格大于栈顶温度。
- 虽有嵌套循环，但每个下标只进栈、出栈各一次，总时间仍是线性。
易错点总结
- 比较写成
>=：[80,80,90]会误认为第二个80更暖；第一个位置的正确答案是2。- 弹栈只用
if：一个高温可能同时解决多天，如[69,71,72]到72时需要连续弹栈。- 栈中只存温度：无法计算等待天数
i - prev，应保存下标。- 写成温度差：
[73,76]的答案是等待 1 天，不是温差 3。- 给未匹配日期填
-1：题目要求没有更暖日期时填0，初始化值已经满足。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 496. 下一个更大元素 I | 简单 | 单调栈结果配合哈希表跨数组查询 |
| 503. 下一个更大元素 II | 中等 | 循环数组遍历两遍下标取模 |
| 1019. 链表中的下一个更大节点 | 中等 | 链表先转数组再套单调栈模板 |
| LCR 038. 每日温度 | 中等 | 同题换壳，检验模板熟练度 |
| 84. 柱状图中最大的矩形 | 困难 | 递增栈同时求左右两侧第一个更小元素 |
| 42. 接雨水 | 困难 | 递减栈出栈时按层横向结算水量 |