LeetCode 739. 每日温度

题目核心

给定数组 temperatures，其中 temperatures[i] 表示第 i 天的温度。

要求返回一个数组 answer，其中 answer[i] 表示从第 i 天开始，要等多少天才会遇到更高温度。

如果之后没有更高温度，则 answer[i] = 0。

例如：

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
answer       = [ 1,  1,  4,  2,  1,  1,  0,  0]

解题思考过程

第一步：理解问题

对每个元素，找到后面第一个比它大的元素的距离。

第二步：暴力解法（嵌套循环）

最直接的思路：对每个元素，向后遍历找第一个更大的元素。

for i from 0 to n-1:
  for j from i+1 to n-1:
    if temperatures[j] > temperatures[i]:
      answer[i] = j - i
      break

时间复杂度：O(n²)
空间复杂度：O(1)

太慢了！需要 O(n) 时间。

第三步：想到单调栈

单调栈是一种特殊的栈，维护栈内元素的单调性。

对于"找下一个更大元素"这类问题，单调栈是最优解法。

单调栈的思路：
- 遍历数组，维护一个单调递减栈
- 栈中存储的是元素的下标
- 当遇到一个比栈顶元素大的元素时：
  - 栈顶元素找到了下一个更大元素
  - 弹出栈顶，计算距离
  - 继续比较新的栈顶
- 当前元素入栈

第四步：验证单调栈过程

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

初始化：stack = [], answer = [0,0,0,0,0,0,0,0]

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

i=1, temp=74:
  74 > 73（temperatures[stack[0]]）
  弹出0，answer[0] = 1 - 0 = 1
  stack为空，入栈1
  stack = [1]

i=2, temp=75:
  75 > 74（temperatures[stack[0]]）
  弹出1，answer[1] = 2 - 1 = 1
  stack为空，入栈2
  stack = [2]

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（temperatures[4]）
  弹出4，answer[4] = 5 - 4 = 1
  72 > 71（temperatures[3]）
  弹出3，answer[3] = 5 - 3 = 2
  72 < 75（temperatures[2]），入栈5
  stack = [2, 5]

i=6, temp=76:
  76 > 72（temperatures[5]）
  弹出5，answer[5] = 6 - 5 = 1
  76 > 75（temperatures[2]）
  弹出2，answer[2] = 6 - 2 = 4
  stack为空，入栈6
  stack = [6]

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

最终：answer = [1, 1, 4, 2, 1, 1, 0, 0] ✓

第五步：为什么单调栈能工作

单调栈维护了一个递减的序列，当遇到更大的元素时，栈中比它小的元素都找到了"下一个更大元素"。

每个元素最多入栈一次，出栈一次，所以时间复杂度是 O(n)。

第六步：Next 数组方法（特殊解法）

题目中温度范围有限（30-100），可以用 Next 数组：

从右往左遍历，维护 next[temp] = 首次出现该温度的日期
对于每个温度，查找比它大的温度中最小的日期

这个方法只适用于温度范围有限的情况。

第七步：方法对比

方法	时间复杂度	空间复杂度	适用场景
单调栈	O(n)	O(n)	通用
Next 数组	O(n*m)	O(m)	m是温度范围

单调栈是通用最优解法！

解法一：Next 数组

官方解法利用了题目的温度范围：30 <= temperatures[i] <= 100。

从右往左遍历数组，维护一个 next 数组：

next[t] 表示温度 t 下一次出现的下标

对于当前温度 temperatures[i]，只需要在所有更高温度中找最近出现的位置：

temperatures[i] + 1 到 100

这些温度范围很小，所以可以直接枚举。

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const next = new Array(101).fill(Number.POSITIVE_INFINITY);

  for (let i = n - 1; i >= 0; i--) {
    let warmerIndex = Number.POSITIVE_INFINITY;

    for (let temp = temperatures[i] + 1; temp <= 100; temp++) {
      warmerIndex = Math.min(warmerIndex, next[temp]);
    }

    if (warmerIndex < Number.POSITIVE_INFINITY) {
      answer[i] = warmerIndex - i;
    }

    next[temperatures[i]] = i;
  }

  return answer;
}

算法思想

从右往左看时，右侧的信息已经处理过。

例如当前位置温度是 73，那么答案一定来自未来某个温度：

74, 75, 76, ..., 100

next 数组记录这些温度在右侧最近一次出现的位置。取其中最小的下标，就是最近的更暖一天。

复杂度

设 n 是天数，W 是温度取值范围。

• 时间复杂度：O(n * W)
• 空间复杂度：O(n + W)

在本题中 W = 71，所以这个解法也可以看作线性时间。

解法二：单调栈

单调栈是这道题最常用的解法。

从右往左遍历，栈里保存的是下标，并且这些下标对应的温度从栈顶到栈底严格递增。

function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length;
  const answer = new Array(n).fill(0);
  const stack: number[] = [];

  for (let i = n - 1; i >= 0; i--) {
    while (
      stack.length > 0 &&
      temperatures[stack[stack.length - 1]] <= temperatures[i]
    ) {
      stack.pop();
    }

    if (stack.length > 0) {
      answer[i] = stack[stack.length - 1] - i;
    }

    stack.push(i);
  }

  return answer;
}

算法思想

对于第 i 天来说，我们要找右侧第一个比它温度高的下标。

如果栈顶下标对应的温度小于等于当前温度，那么这个栈顶下标不可能成为当前天的答案：

• 它不比当前天更暖。
• 它还比当前天更靠右，所以对更左边的天来说，当前天也会比它更有竞争力。

因此可以直接弹出。

弹出所有小于等于当前温度的下标后：

• 如果栈为空，说明右侧没有更暖的一天。
• 如果栈不为空，栈顶就是右侧最近的更暖一天。

最后把当前下标入栈，供更左边的天使用。

从左往右的等价写法

当前 739.ts 使用的是从左往右的单调栈。

这种写法维护的是“还没有找到更暖一天的下标”。当当前温度比栈顶下标的温度更高时，就说明当前天是栈顶那一天的答案。

function dailyTemperatures(temperatures: number[]): number[] {
  const stack: number[] = [];
  const answer = new Array(temperatures.length).fill(0);

  for (let i = 0; i < temperatures.length; i++) {
    while (
      stack.length > 0 &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const previousIndex = stack.pop()!;
      answer[previousIndex] = i - previousIndex;
    }

    stack.push(i);
  }

  return answer;
}

这和从右往左的官方单调栈本质相同，只是更新答案的时机不同：

• 从右往左：先删掉无用候选，再让当前天查栈顶。
• 从左往右：当前天负责解决栈里比自己冷的旧下标。

为什么栈是单调的

以从左往右写法为例，栈中下标对应的温度会保持从栈底到栈顶递减。

如果当前温度更高，就不断弹出较冷的旧下标，并为它们写入答案。

弹出结束后，栈顶温度一定大于等于当前温度，然后当前下标入栈，所以单调性继续成立。

两种官方解法对比

解法	时间复杂度	空间复杂度	特点
Next 数组	O(n * W)	O(n + W)	利用温度范围固定，思路直接
单调栈	O(n)	O(n)	每个下标最多入栈出栈一次，最通用

面试中优先写单调栈。它不依赖温度范围是否很小，也能推广到“下一个更大元素”类问题。