Hot 100 --- 每日温度

本文概览：本文讲解每日温度的核心思路：用单调栈优化暴力遍历，从 O(n²) 降到 O(n)

一、题目

二、题目分析

1. 题目要求

给定一个温度数组 temperatures，返回一个同样长度的数组 answer，其中 answer[i] 表示第 i 天到下一个更高温度的天数。如果之后都不会升高，用 0 代替。

例子：temperatures = [73, 74, 75, 71, 72, 76, 73]

第 0 天：73 → 第 1 天 74 更高 → answer[0] = 1
第 1 天：74 → 第 2 天 75 更高 → answer[1] = 1
第 2 天：75 → 第 5 天 76 更高 → answer[2] = 3
第 3 天：71 → 第 4 天 72 更高 → answer[3] = 1
第 4 天：72 → 第 5 天 76 更高 → answer[4] = 1
第 5 天：76 → 之后没有更高的 → answer[5] = 0
第 6 天：73 → 之后没有更高的 → answer[6] = 0

结果：[1, 1, 3, 1, 1, 0, 0]

2. 暴力思路的问题

最直觉的做法：对每个位置，往后遍历找到第一个更高的温度。

for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        if (temperatures[j] > temperatures[i]) {
            answer[i] = j - i;
            break;
        }
    }
}

时间复杂度：O(n²)，最坏情况下（温度递减）会超时。

3. 核心观察：暴力遍历中的浪费

关键问题：暴力遍历中，我们其实获取了很多信息，但没有利用。

例子：温度数组 [76, 68, 72, 77]

从 76 开始往后遍历：

遍历到 68：
  68 < 76，不是，但记录下来

遍历到 72：
  72 > 68，所以 68 的结果已经知道了（72 - 68 的天数）
  72 < 76，继续

遍历到 77：
  77 > 72，所以 72 的结果也知道了
  77 > 76，所以 76 的结果也知道了

一次遍历，找到了 3 个结果！

问题：在暴力方法中，这些中间结果完全被浪费了。68 和 72 的结果在遍历 76 时就已经确定了，但暴力方法会在后面重新遍历一遍。

优化思路：边遍历边比较，已经遍历过的温度如果能确定结果，就立即回填，不要等到后面再遍历。

三、思路概览

public int[] dailyTemperatures(int[] temperatures) {
    if (temperatures.length == 0) {
        return new int[0];
    }
    // 单调栈
    Deque<Integer> stack = new ArrayDeque<>();
    int[] result = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        // 栈空，直接入栈
        if (stack.isEmpty()) {
            stack.push(i);
            continue;
        }   
        // 栈非空，比较温度
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            // 出栈
            int index = stack.pop();
            // 计算天数
            result[index] = i - index;
        }
        // 入栈
        stack.push(i);
    }
    // 栈中剩余的元素，天数为0
    while (!stack.isEmpty()) {
        int index = stack.pop();
        result[index] = 0;
    }
    return result;
}

思路简要说明：

栈存储索引：存索引而不是温度值，这样可以 O(1) 获取温度，还能直接算出天数差
单调递减栈：栈内温度从底到顶递减
遍历过程：
- 新温度 > 栈顶温度：栈顶出栈，回填结果（天数 = 当前索引 - 出栈索引）
- 重复直到栈顶温度 >= 新温度，或栈为空
- 新温度索引入栈
遍历结束后：栈内剩余的元素就是之后没有更高温度的天，结果为 0

四、思路详解

第一步：怎么实现"边遍历边比较"？

从上面的分析我们知道，需要边遍历边回填已经确定的结果。那么问题来了：怎么实现？

需求：

需要记住还没找到更高温度的那些天
每次遍历到新温度时，和记住的那些天比较
如果新温度更高，就回填结果，并从记住的列表中删除

数据结构：栈！

栈里存储还没找到更高温度的天的索引
每次遍历到新温度时，和栈顶比较
如果新温度更高，栈顶出栈并回填结果
重复这个过程，直到栈顶温度 >= 新温度，或栈为空
然后把新温度的索引入栈

第二步：为什么是单调栈？

单调栈：栈内元素从栈底到栈顶单调递减（或递增）。

这题为什么用递减栈？

因为我们要找"下一个更高的温度"，所以栈里存的是还没找到更高温度的天。如果新温度比栈顶高，栈顶就找到答案了，出栈。

栈的特性：

栈底：最早遍历的，温度最高（或相等）
栈顶：最晚遍历的，温度最低
每次新温度入栈前，会把所有比它低的栈顶弹出

这样栈内温度从底到顶递减，就是单调递减栈。

第三步：为什么栈里存索引而不是温度值？

存索引的好处：

可以通过 temperatures[index] 获取温度值
可以直接算出天数差：i - index

如果存温度值：还需要额外记录这个温度是哪一天的，多了一步操作。

第二步：单调栈的工作原理

核心思想：每次遍历到新温度时，把所有比它低的栈顶弹出并回填结果。

为什么可以这样做？

因为栈内温度从底到顶递减，如果新温度比栈顶高，栈顶就找到了"下一个更高的温度"，可以立即回填结果。

例子：栈内 [76, 72, 68]（栈顶是 68），新温度 77

77 > 68，68 出栈，回填结果
77 > 72，72 出栈，回填结果
77 > 76，76 出栈，回填结果
栈为空，77 入栈

一次遍历，找到了 3 个结果！

第三步：为什么是 O(n) 而不是 O(n²)？

看起来有 while 循环，应该是 O(n²)？

实际上：每个索引最多入栈一次，出栈一次。

外层 for 循环：n 次
内层 while 循环：所有索引总共出栈 n 次

所以总操作次数是 2n，时间复杂度 O(n)。

第四步：遍历结束后栈内剩余的元素

遍历结束后，栈内还有元素，说明这些天之后没有更高的温度了，结果为 0。

例子：温度数组 [76, 72, 68]

76 入栈：stack = [76]
72 < 76，72 入栈：stack = [76, 72]
68 < 72，68 入栈：stack = [76, 72, 68]

遍历结束，栈内还有 3 个元素
result[76的索引] = 0
result[72的索引] = 0
result[68的索引] = 0

完整执行过程

以 temperatures = [73, 74, 75, 71, 72, 76, 73] 为例：

初始：stack = [], result = [0, 0, 0, 0, 0, 0, 0]

i=0, temp=73：
  栈为空，73 入栈
  stack = [0]（存索引，对应温度 73）

i=1, temp=74：
  74 > 73，栈顶 0 出栈
  result[0] = 1 - 0 = 1
  栈为空，74 入栈
  stack = [1]

i=2, temp=75：
  75 > 74，栈顶 1 出栈
  result[1] = 2 - 1 = 1
  栈为空，75 入栈
  stack = [2]

i=3, temp=71：
  71 < 75，71 入栈
  stack = [2, 3]（栈底 75，栈顶 71）

i=4, temp=72：
  72 > 71，栈顶 3 出栈
  result[3] = 4 - 3 = 1
  72 < 75，72 入栈
  stack = [2, 4]（栈底 75，栈顶 72）

i=5, temp=76：
  76 > 72，栈顶 4 出栈
  result[4] = 5 - 4 = 1
  76 > 75，栈顶 2 出栈
  result[2] = 5 - 2 = 3
  栈为空，76 入栈
  stack = [5]

i=6, temp=73：
  73 < 76，73 入栈
  stack = [5, 6]（栈底 76，栈顶 73）

遍历结束，栈内还有元素：
  result[5] = 0
  result[6] = 0

最终结果：[1, 1, 3, 1, 1, 0, 0] ✓

再以 temperatures = [30, 40, 50, 60] 为例（递增序列）：

初始：stack = [], result = [0, 0, 0, 0]

i=0, temp=30：
  栈为空，30 入栈
  stack = [0]

i=1, temp=40：
  40 > 30，栈顶 0 出栈
  result[0] = 1 - 0 = 1
  栈为空，40 入栈
  stack = [1]

i=2, temp=50：
  50 > 40，栈顶 1 出栈
  result[1] = 2 - 1 = 1
  栈为空，50 入栈
  stack = [2]

i=3, temp=60：
  60 > 50，栈顶 2 出栈
  result[2] = 3 - 2 = 1
  栈为空，60 入栈
  stack = [3]

遍历结束，栈内还有元素：
  result[3] = 0

最终结果：[1, 1, 1, 0] ✓

五、总结

每日温度的核心思路：

单调栈：栈内温度从底到顶递减
栈存储索引：方便获取温度值和计算天数差
遍历过程：新温度 > 栈顶温度时，栈顶出栈并回填结果
**时间复杂度 O(n)**：每个索引最多入栈一次，出栈一次
**空间复杂度 O(n)**：栈最多存储 n 个索引

单调栈的适用场景：

找"下一个更大/更小的元素"
需要维护一个单调序列
暴力遍历中有重复计算，可以优化