056 · Daily Temperatures

algorithm

Published

July 9, 2026

My First Thoughts

嗯，这题看起来和前面的单调栈题是同一个类型。

之前 Final Prices With a Special Discount in a Shop 是找右边第一个小于或等于当前值的价格，也就是某种 next smaller。

这一题是找右边第一个更高的温度，也就是 next higher。

之前是找到那个值以后，算一个值的差：

prices[old_i] -= prices[i]

现在是找到更高温度以后，算位置的差：

result[old_i] = i - old_i

所以整体感觉是一样的。

题目给的是：

temperatures

需要一个栈保存还没有找到更高温度的那些天：

stack = []

因为答案长度和 temperatures 一样，而且如果某一天之后没有更暖和的日子，答案本来就是 0，所以可以先创建一个同样长度、全是 0 的结果数组：

result = [0] * len(temperatures)

然后从左到右遍历：

for i in range(0, len(temperatures)):

如果当前温度比栈顶那一天的温度更高：

temperatures[i] > temperatures[stack[-1]]

说明当前这一天就是栈顶那一天一直在等的更暖和的日子。

于是可以回填答案：

result[stack[-1]] = i - stack[-1]

再把那一天从栈里弹出来：

stack.pop()

这里也和前面的题一样，要用 while，因为同一个更高温度可能同时解决前面好几天。

比如：

temperatures = [70, 71, 72]

看到 72 的时候，它可以解决 71；如果前面还有更低的温度，也可能继续解决。

整理一下，代码就是：

stack = []
result = [0] * len(temperatures)

for i in range(0, len(temperatures)):
    while stack and temperatures[i] > temperatures[stack[-1]]:
        result[stack[-1]] = i - stack[-1]
        stack.pop()

    stack.append(i)

return result

Why That Is Not Enough

这个思路已经是正解了。

这个尝试本身没有方向问题，算法已经成立。

真正需要补清楚的是两个状态含义。

第一，stack 里保存的是下标，不是温度值。

因为最后要填的是：

result[某一天] = 等待天数

如果栈里只保存温度值，比如 73、74，我们就不知道应该回到 result 的哪个位置去更新答案。

保存下标以后，两件事都能做：

temperatures[stack[-1]]

用来拿到那一天的温度做比较。

result[stack[-1]]

用来回到那一天的位置填写答案。

第二，result = [0] * len(temperatures) 是适合这题的。

这题的答案数组长度一开始就确定，而且默认值正好就是 0：如果后面没有更暖和的日子，这个位置最后就应该保持 0。

所以我们不用等到最后再补零，也不用把所有剩余的栈元素再处理一遍。

Final Idea

用一个栈 stack 保存：

已经看过，但是还没有找到右边第一个更高温度的天数下标。

再准备一个结果数组：

result = [0] * len(temperatures)

这里的 0 表示“目前还没有找到更暖和的日子”。如果之后真的找到了，就把它改成等待天数；如果一直没找到，就保留 0。

从左到右遍历 temperatures。

当走到第 i 天时，如果当前温度比栈顶那一天更高：

temperatures[i] > temperatures[stack[-1]]

那么第 i 天就是栈顶那一天等到的第一个更暖和的日子。

等待天数就是两个下标的差：

i - stack[-1]

所以更新：

result[stack[-1]] = i - stack[-1]

然后弹出栈顶。

这里继续用 while，因为当前这一天可能不只解决最近的一天，也可能继续解决更早的几天。

最后把当前下标 i 放入栈中，表示这一天自己也开始等待右边的更高温度。

Why It Works

栈里保存的下标，对应的是还没有找到答案的天。

从左到右遍历时，当前第 i 天一定在栈里所有下标的右边。

如果：

temperatures[i] > temperatures[stack[-1]]

说明当前这一天比栈顶那一天更暖和。

为什么它是“第一个”更暖和的日子？

因为栈顶那一天从入栈到现在，中间经过的每一天都没有把它弹出来。也就是说，中间那些温度都没有比它高。现在第一次遇到一个更高的温度，所以当前下标 i 就是它要等到的第一个更暖和的日子。

弹出以后，还要继续检查新的栈顶。

比如：

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]

过程里会出现这种情况：

看到 72 时，它可以解决 69，也可以继续解决 71
看到 76 时，它可以解决 72，也可以继续解决 75

所以必须是 while，不是 if。

遍历结束后，栈里剩下的下标都没有等到更高温度。它们在 result 里本来就是 0，不用额外修改。

Code

def dailyTemperatures(temperatures):
    stack = []
    result = [0] * len(temperatures)

    for i in range(len(temperatures)):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            old_i = stack.pop()
            result[old_i] = i - old_i

        stack.append(i)

    return result

这里把 stack.pop() 的结果先放到 old_i 里，是为了避免重复写 stack[-1]，也让“被当前天解决的是哪一天”更清楚。

Complexity

Time	\(O(n)\) - `n` 是 `temperatures` 的长度；每个下标最多入栈一次、出栈一次
Space	\(O(n)\) - `result` 需要保存答案，`stack` 最坏情况下会保存所有下标

Takeaway

单调栈题里，如果答案需要回填到原来的位置，栈里优先保存下标。比较时通过下标取值，更新答案时也通过下标回到对应位置。像这题这种“没找到就返回 0”的场景，可以先建一个全是 0 的定长结果数组，再只改那些已经找到答案的位置。

← Quiz