LeetCode LCR 038. 每日温度
题目描述
题意分析
对每一天
i，找到右侧第一个满足temperatures[j] > temperatures[i]的位置j，返回等待天数j - i；找不到时返回 $0$。温度必须严格更高，相等不能作为答案。每天分别向右扫描，最坏需要 $O(n^2)$ 时间。可以把尚未找到答案的日期集中保存，让新的一天一次解决所有能被它满足的等待者。
解法：单调栈维护候选
核心思路
[!blue]
栈中保存尚未遇到更高温度的下标，下标从栈底到栈顶递增，对应温度单调不增。存下标既能查回温度，也能在找到答案时计算相隔天数。
扫描到第
i天，只要今天温度严格高于栈顶那天，就弹出下标j，令answer[j] = i - j。今天可能同时满足多个等待者，因此要连续弹栈。若栈顶温度已不低于今天，栈内更下面的温度也不低于今天，便可以停止，再把i入栈。弹出时得到的一定是第一个更高温度：从
j到i之间的日期都已按顺序处理，若此前出现过更高温度，j早就会被结算，不可能还留在栈中。弹完后栈顶温度不小于今天，再压入i，也保持了单调不增的性质。相等温度要同时留栈，等待之后真正升温。扫描结束仍在栈中的日期没有更高温度，答案保留数组初始值 $0$；最后一天也一定为 $0$。
解题步骤
- 创建全零的结果数组和空下标栈。
- 从左到右扫描，每当当前温度高于栈顶温度，就弹出下标并写入下标差。
- 重复弹栈，直到栈空或栈顶温度不低于当前温度。
- 将当前下标入栈，继续处理下一天。
- 返回结果，无需再次清空栈。严格递增时除最后一天外答案均为 $1$；严格递减或全相等时答案均为 $0$。
代码实现
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
// 默认全 0，正好对应「之后再无更高温度」。
int[] answer = new int[n];
// 栈里存下标，温度自底向上单调不增，含义是「还没等到更高温度的日子」。
Deque<Integer> stk = new ArrayDeque<>();
for (int i = 0; i < n; ++i) {
// 严格小于才结算，相同温度不算「更高」。
while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]) {
int j = stk.pop();
answer[j] = i - j;
}
stk.push(i);
}
return answer;
}
}
func dailyTemperatures(temperatures []int) []int {
// 默认全 0，正好对应「之后再无更高温度」。
answer := make([]int, len(temperatures))
// 栈里存下标，温度自底向上单调不增。
var stk []int
for i, t := range temperatures {
// 严格小于才结算，相同温度不算「更高」。
for len(stk) > 0 && temperatures[stk[len(stk)-1]] < t {
j := stk[len(stk)-1]
answer[j] = i - j
stk = stk[:len(stk)-1]
}
stk = append(stk, i)
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。每个下标入栈一次、至多出栈一次，所有内层循环的弹栈次数合计不超过 $n$。
- 空间复杂度：$O(n)$，不计结果数组。温度持续不升时，所有下标都会留在栈中。
关键点总结
[!green]
- 栈保存未解决的日期，温度从栈底到栈顶单调不增。
- 当前温度严格更高才结算，弹出时直接得到最近的升温日。
- 每个下标只结算一次，剩余答案保持 $0$。
易错点总结
[!yellow]
- 栈存下标，弹栈后才能用当前下标减旧下标计算等待天数。
- 只有严格升温才弹栈，相同温度继续等待。
- 先结算所有更低温的栈顶，再将当前下标入栈；先入栈会挡住旧候选。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 496. 下一个更大元素 I | 简单 | 同样寻找右侧第一个更大元素，本题返回距离，所以栈中保存下标。 |
| 503. 下一个更大元素 II | 中等 | 原题数组首尾相接，需要再次扫描来补足跨边界的更大值，本题只向右查找。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！