Daily Temperatures

对于每天，求还要等几天才会升温。

对每一天，返回还要等多少天才会升温。这是最经典的“下一个更大元素”索引题。

ArrayMonotonic Stack

题目定位

每一天都在找右侧第一个严格更大的值，这正是最标准的单调栈触发条件。

关键观察

把尚未找到更高温度的下标放进递减栈；当前更高温度会一次性解决它后面所有更小温度。

目标复杂度

O(n) / O(n)

这题的解法思路怎么拆

维护一个单调递减栈，里面放还没找到更高温度的日期下标。

当更高温度出现时，它会依次解决栈顶所有更低温度的日期。

把这些下标弹出，并立刻计算等待天数。

等所有更低温度处理完，再把当前下标压栈。

拿一个例子顺一遍

例如 [73, 74, 75, 71, 69, 72, 76, 73]。

74 出现时解决 73，所以 answer[0] = 1；75 出现时解决 74，所以 answer[1] = 1。

后面的 72 会解决 69 和 71，再由 76 解决 72 和 75。

最后还留在栈里的下标，说明后面再也没有更高温度，因此答案保持 0。

参考实现

Python

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    answer = [0] * len(temperatures)
    stack: list[int] = []

    for index, value in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < value:
            previous = stack.pop()
            answer[previous] = index - previous
        stack.append(index)

    return answer

TypeScript 版本

TypeScript

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

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

  return answer;
}