实战：每日温度 ​

给你一组每日温度数据，你想知道：对于每一天，需要等几天才能等到更暖和的天气？

比如温度是 [73, 74, 75, 71, 69, 72, 76, 73]：

• 第 0 天是 73°，第 1 天是 74° > 73°，所以等 1 天
• 第 2 天是 75°，要到第 6 天的 76° 才更高，等 4 天
• 第 6 天是 76°，之后没有更高的了，答案是 0

这道题引出了一个重要的算法模式——单调栈。

问题描述 ​

LeetCode 739. Daily Temperatures

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例：

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

问题分析 ​

首先思考暴力解法：对于每一天，向后遍历找第一个更高的温度。

// 暴力解法 O(n²)
function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (temperatures[j] > temperatures[i]) {
        answer[i] = j - i;
        break;
      }
    }
  }
  
  return answer;
}

时间复杂度 O(n²)，有没有更好的方法？

现在问一个问题：当我们遍历到一个新的温度时，它可能是谁的答案？

答案是：它可能是之前所有比它低的温度的答案！

这个洞察引出了单调栈的思路。

单调栈解法 ​

核心思想：维护一个单调递减栈（栈中温度从底到顶递减），栈中存储的是索引。

遍历每一天：

1. 当前温度比栈顶温度高 → 栈顶找到了答案，弹出
2. 重复上述过程，直到栈为空或栈顶温度 >= 当前温度
3. 将当前索引入栈

function dailyTemperatures(temperatures) {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const stack = [];  // 存储索引，对应的温度单调递减
  
  for (let i = 0; i < n; i++) {
    // 当前温度比栈顶对应的温度高
    while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const prevIndex = stack.pop();
      answer[prevIndex] = i - prevIndex;
    }
    stack.push(i);
  }
  
  return answer;
}

执行过程可视化 ​

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

索引：          0   1   2   3   4   5   6   7
温度：         73  74  75  71  69  72  76  73

遍历过程：

i=0, temp=73:
  栈空，直接入栈
  stack = [0]

i=1, temp=74:
  74 > 73（栈顶索引0对应的温度）
  弹出 0，answer[0] = 1-0 = 1
  栈空，入栈
  stack = [1]
  answer = [1,0,0,0,0,0,0,0]

i=2, temp=75:
  75 > 74（栈顶索引1对应的温度）
  弹出 1，answer[1] = 2-1 = 1
  栈空，入栈
  stack = [2]
  answer = [1,1,0,0,0,0,0,0]

i=3, temp=71:
  71 < 75，直接入栈
  stack = [2, 3]

i=4, temp=69:
  69 < 71，直接入栈
  stack = [2, 3, 4]

i=5, temp=72:
  72 > 69（栈顶索引4对应的温度）
  弹出 4，answer[4] = 5-4 = 1
  72 > 71（栈顶索引3对应的温度）
  弹出 3，answer[3] = 5-3 = 2
  72 < 75，入栈
  stack = [2, 5]
  answer = [1,1,0,2,1,0,0,0]

i=6, temp=76:
  76 > 72（栈顶索引5对应的温度）
  弹出 5，answer[5] = 6-5 = 1
  76 > 75（栈顶索引2对应的温度）
  弹出 2，answer[2] = 6-2 = 4
  栈空，入栈
  stack = [6]
  answer = [1,1,4,2,1,1,0,0]

i=7, temp=73:
  73 < 76，直接入栈
  stack = [6, 7]

遍历结束，栈中剩余的索引（6, 7）没有更高温度，answer 保持 0

最终结果：[1,1,4,2,1,1,0,0]

为什么存索引而不是存温度？ ​

因为我们需要计算天数差，需要知道位置信息。

// 存索引
answer[prevIndex] = i - prevIndex;  // 可以计算距离

// 如果只存温度，就不知道它是第几天了

为什么是单调递减栈？ ​

假设栈中有温度 [75, 71, 69]（从底到顶），这意味着什么？

• 75 还在等更高的温度
• 71 也在等更高的温度
• 69 也在等

它们都在等一个比自己高的温度。当新温度出现时：

• 如果新温度 <= 69，三个都继续等
• 如果新温度 > 69 但 <= 71，69 找到了答案，75 和 71 继续等
• 如果新温度 > 75，三个都找到了答案

单调递减保证了：一旦出现更高温度，可以快速确定谁找到了答案。

复杂度分析 ​

• 时间复杂度：O(n)。虽然有嵌套循环，但每个元素最多入栈一次、出栈一次，总操作次数不超过 2n。
• 空间复杂度：O(n)。栈的大小最坏情况下是 n（温度递减时）。

边界情况 ​

• 温度递增：[30,40,50,60] → [1,1,1,0]，每天只等 1 天
• 温度递减：[60,50,40,30] → [0,0,0,0]，没有更高的温度
• 全部相同：[50,50,50] → [0,0,0]，相等不算更高
• 单个元素：[50] → [0]

常见错误 ​

错误1：存温度而不是索引

// ❌ 无法计算天数差
stack.push(temperatures[i]);
// 后面怎么计算 answer[?] = i - ? 呢？

错误2：用 if 而不是 while

// ❌ 可能漏掉多个需要弹出的元素
if (temperatures[i] > temperatures[stack[stack.length - 1]]) {
  // 只弹出一个
}

// ✅ 要用 while，可能连续弹出多个
while (stack.length > 0 && temperatures[i] > temperatures[stack[stack.length - 1]]) {
  // 弹出所有比当前温度低的
}

错误3：忘记处理栈中剩余元素

其实不需要额外处理，因为 answer 数组初始化为 0，剩余元素自然是 0。

技巧总结 ​

单调栈解决"下一个更大/更小元素"问题：

• 单调递减栈：找下一个更大元素
• 单调递增栈：找下一个更小元素
• 存储索引：需要计算距离时
• 存储值：只需要知道值是什么时

这道题是单调栈的入门经典。掌握后，你可以轻松处理接雨水、柱状图最大矩形等问题。

关联题目 ​

• LeetCode 496：下一个更大元素 I
• LeetCode 503：下一个更大元素 II（循环数组）
• LeetCode 84：柱状图中最大的矩形