LC739　每日温度¶

中等通过率 69.7%python3核心代码模式栈样例通过牛客 AC栈数组单调栈

牛客原题　源码

讲解章节：单调栈

一句话

单调递减栈存下标，把「下一个更大元素」一次扫描全部解决。

解题思路¶

这题考什么¶

要为每一天求出「右边第一个更高温度出现在几天后」。对每天现往右找是 O(n^2)，n = 1e5 时是 1e10 次比较，Python 下没有可能。

关键观察是一条淘汰规则：

若 i < j 且 temperatures[i] <= temperatures[j]，
那么对任何 j 右边的位置来说，i 都是没用的——
因为它要找的答案，j 会比它先被满足（j 更靠右且不更矮）。

换个说法：还在等待答案的那些天，温度必然是从左到右递减的。一旦出现左边不高于右边的情况，左边那天当场就被右边这天解决掉了。于是把「尚未找到答案的下标」放进一个栈，栈内温度自底向上严格递减，这就是单调栈（见单调栈）。

扫描到第 i 天，温度 t：只要栈非空且栈顶那天的温度 < t，就说明第 i 天正是它等待的答案，弹出并记下 answer[栈顶] = i - 栈顶（相隔的天数）；反复弹到栈顶温度不低于 t 为止，再把 i 压进去等待它自己的答案。扫完仍留在栈里的下标，右边再没有更高的温度，答案保持初值 0。

栈里存的是下标而不是温度：答案要的是「几天后」，也就是两个位置之差，只有下标能回答这个问题；温度随时可以用 temperatures[下标] 取回来。

每个下标入栈一次、出栈一次，总操作 2n 次，所以是 O(n) 而不是 O(n^2)。

数据规模与复杂度¶

1 <= temperatures.length <= 1e5，30 <= temperatures[i] <= 100。时间 O(n)，空间 O(n)——温度单调不增（如 100, 99, 98, …）时栈会装下全部下标。值域只有 71 种取值，也可以按「记录每个温度最近一次出现的位置，查询时扫 71 个更高的温度取最近」来做，同样是线性级；但单调栈不依赖值域窄这个特殊条件，是更通用的解法。

坑在哪¶

栈里存下标，不存温度。答案是天数之差，存温度就无从相减。
弹栈条件用严格小于。相等的温度不算「更高」，题面要的是「下一个更高温度」。写成 <= 会把等温的那天误判为已解决， [73, 73, 74] 的第 0 天答案会错成 1，正确答案是 2。这一点与 LC239 滑动窗口最大值恰好相反：那题求最大值，相等时弹掉旧的是安全的；这题求严格更大者，弹掉就是错的。
答案数组初值必须是 0，对应题面「之后都不会升高就填 0」。扫完后还留在栈里的下标从来不会被赋值，全靠这个初值兜底。
记录的是 i - 栈顶，不是 i。题面问的是「几天后」这个间隔，不是绝对日期。写成 i 会让第一个样例输出 [1, 2, 6, 5, 5, 6, 0, 0]。
弹栈要用 while 而不是 if。一个高温可以一次性解决掉栈里多天， [30, 40, 50, 60] 里的 60 不需要连弹，但 [75, 71, 69, 72] 里的 72 必须连弹 69 和 71 两天；写成 if 只弹一层，剩下的答案永远补不上。
严格比对：每天的等待天数唯一，输出顺序也由日期定死，没有多解。

样例复核¶

temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，期望 [1, 1, 4, 2, 1, 1, 0, 0]。栈内容以「下标(温度)」表示，answer 初始全 0：

i=0 t=73  栈空 -> 入          栈 = [0(73)]
i=1 t=74  74 > 73 弹 0，ans[0] = 1 - 0 = 1；入 1   栈 = [1(74)]
i=2 t=75  75 > 74 弹 1，ans[1] = 2 - 1 = 1；入 2   栈 = [2(75)]
i=3 t=71  71 < 75 直接入      栈 = [2(75), 3(71)]
i=4 t=69  69 < 71 直接入      栈 = [2(75), 3(71), 4(69)]
i=5 t=72  弹 4，ans[4] = 5 - 4 = 1；弹 3，ans[3] = 5 - 3 = 2；
          72 < 75 停，入 5    栈 = [2(75), 5(72)]
i=6 t=76  弹 5，ans[5] = 6 - 5 = 1；弹 2，ans[2] = 6 - 2 = 4；
          栈空，入 6          栈 = [6(76)]
i=7 t=73  73 < 76 直接入      栈 = [6(76), 7(73)]

扫完栈里剩 6 和 7，它们的答案保持初值 0。输出 [1, 1, 4, 2, 1, 1, 0, 0]，与题面一致。i=5 那一步连弹两层，正是「必须用 while 而不是 if」的现场。

参考实现¶

solutions/leetcode/LC739/sol.py
from typing import List, Optional


class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        # 初值 0 对应题面「之后都不会升高就填 0」：扫完仍留在栈里的下标
        # 从来不会被赋值，全靠这个初值兜底
        answer = [0] * n
        # 单调栈：存**下标**，对应温度自底向上严格递减。
        # 存下标而非温度，是因为答案要的是两个位置之差（几天后）。
        # 栈里装的正是「还在等待更高温度」的那些天
        stack = []
        for i in range(n):
            t = temperatures[i]
            # 用 while 连弹：一个高温可以一次解决掉栈里连续多天。
            # 条件是严格小于——题面要的是「更高」，等温不算，
            # 写成 <= 会把等温那天误判为已解决
            while stack and temperatures[stack[-1]] < t:
                # 第 i 天正是栈顶那天等待的答案，间隔天数是两个下标之差
                j = stack.pop()
                answer[j] = i - j
            # 第 i 天自己的答案还没出现，入栈排队等待
            stack.append(i)
        return answer

LC739 每日温度¶