如何用单调栈解决每日温度问题？

简化版

每日温度要找每一天右侧第一个更高温度，可以用单调递减栈存下标。当前温度比栈顶温度高时，栈顶那天的答案就是 i - stackTop；每个下标最多入栈出栈一次，时间复杂度 O(n)。

详细版

暴力做法对每一天向右扫描，最坏 O(n²)。单调栈把“还没等到更高温度的天”放进栈里，并让栈内温度从栈底到栈顶保持递减。遍历到第 i 天时，如果 temperatures[i] 更高，就持续弹出栈顶下标 j，令 answer[j] = i - j。

int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] ans = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int j = stack.pop();
            ans[j] = i - j;
        }
        stack.push(i);
    }
    return ans;
}

栈里存下标而不是温度，是因为答案要计算等待天数。没有更高温度的下标最终留在栈里，对应答案保持默认值 0。

完整版教学

一、题目到底在问什么

给定温度数组 temperatures，第 i 个位置要找的是右边第一个比 temperatures[i] 大的位置 j，答案是距离 j - i。如果右边再也没有更高温度，答案就是 0。这个问题的关键不是“找最大值”，而是找“第一个更大值”，所以离当前位置最近的那个更高温度一旦出现，答案就立刻确定。

例如 [73,74,75,71,69,72,76,73] 的答案是 [1,1,4,2,1,1,0,0]。第 2 天温度 75，要等到第 6 天 76，距离是 4；第 6 天 76 后面没有更高温度，所以是 0。

二、为什么暴力会慢

暴力做法是每个位置向右找更高温度。对于严格递减数组 [80,79,78,77,76]，第 0 个要看 4 次，第 1 个要看 3 次，第 2 个要看 2 次，总比较次数接近 n(n-1)/2，复杂度 O(n²)。当 n 到 100000 时，这会变成几十亿级比较。

第0天: 看 1,2,3,4...
第1天: 看 2,3,4...
第2天: 看 3,4...

单调栈的优化点是：某个下标一旦等到了更高温度，就不再参与后续比较；没有等到的下标才继续留在栈里。

三、单调栈保存什么不变量

栈里保存“还没有找到答案的下标”，并且这些下标对应的温度从栈底到栈顶单调递减。当前温度如果比栈顶高，就说明栈顶那天终于等到了第一个更高温度，因为当前天是从左到右扫描过程中最早出现的更高温度。

温度: 73 74 75 71 69 72
扫描到 72 前，栈可能是: [75的下标, 71的下标, 69的下标]
72 到来后: 69 被解决，71 被解决，75 仍未解决

这个不变量让我们只需要比较栈顶。栈顶比当前小就弹出；弹完后新的栈顶仍然代表最近一批未解决候选。

四、手算一遍流程

以 [73,74,75,71,69,72] 为例：

i	当前温度	操作	已确定答案
0	73	0 入栈	-
1	74	弹 0，1 入栈	ans[0]=1
2	75	弹 1，2 入栈	ans[1]=1
3	71	3 入栈	-
4	69	4 入栈	-
5	72	弹 4、弹 3，5 入栈	ans[4]=1, ans[3]=2

注意第 2 天的 75 没被 72 弹掉，因为 72 不比 75 高。它继续等待后面的 76，这正是单调递减栈能保留有效候选的原因。

五、代码边界怎么写稳

栈存下标，比较时用 temperatures[stack.peek()]。结果数组初始化为 0，这样没有更高温度的日期不用额外处理。循环条件必须是 temperatures[i] > temperatures[stack.peek()]，不是 >=，因为题目要“更高温度”，相同温度不能解决栈顶。

while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
    int prev = stack.pop();
    ans[prev] = i - prev;
}
stack.push(i);

复杂度公式可以这样理解：

总操作次数 <= n 次入栈 + n 次出栈
时间复杂度 = O(n)
额外空间 = O(n)

六、常见误区与追问

记忆钩子：每日温度不是维护窗口最大值，而是“谁等到了第一个更热的未来”。栈里放的是还没等到的人，当前温度负责给他们结算答案。

误区：栈里存温度就够了。 答案要计算等待天数，必须知道原始下标；温度只能辅助比较。
误区：相等温度也可以弹出。 题目要求更高温度，相等不能让等待结束，所以条件是 >。
误区：while 会导致 O(n²)。 每个下标只会被弹出一次，所有 while 的总弹出次数不超过 n。
追问：为什么是单调递减栈？ 因为要找右侧第一个更大值，当前值更大时才能解决栈顶，未解决候选自然保持递减。
追问：如果问右侧第一个更低温度怎么办？ 改成单调递增栈，当前温度更低时弹出栈顶。
追问：为什么没答案的位置是 0？ 这些位置遍历结束后仍在栈里，说明右侧没有更高温度，默认 0 正好符合题意。

七、加强记忆

每日温度的核心链条是：题目要“右侧第一个更高” -> 暴力重复扫描 -> 用单调递减栈保存未解决下标 -> 当前温度更高时批量弹栈结算距离。记住“栈里的人都还没等到更热的一天”，就能自然推出存下标、用 >、答案为 i - j 和 O(n) 复杂度。

简化版

详细版