LeetCode LCR 038. 每日温度

约 8 分钟
文章信息 5 个分类 4 个标签
分类
LeetCode 中等 119 经典题变种挑战 剑指 Offer 剑指 Offer（专项突击版）
标签
数组 LCR 栈 单调栈
目录

题目描述

✅ LCR 038. 每日温度

题意分析

给一个每日温度数组，对每一天求「还要等多少天才会遇到更高的温度」，若之后再无更高温度则填 0。

题意可以精确改写成：对每个下标 i，找出满足 j > i 且 temperatures[j] > temperatures[i] 的最小 j，答案是 j - i。这是「下一个更大元素」的标准形式，只是返回的是距离而不是值。

有两点必须严格对待。其一，是严格更大，温度相同不算，[70, 70, 71] 中第 0 天要等到第 2 天。其二，返回的是下标之差而不是元素值，所以中间结构里存的应该是下标，只有下标才能同时算出距离和查回温度。

约束里数组长度可达十万级，$O(n^2)$ 的两重循环在最坏情况（严格递减数组）下要跑五十亿次，必然超时，这是在提示需要线性解法。

边界：单个元素的答案是 0；严格递减数组的答案全是 0；严格递增数组的答案全是 1；相等元素连续出现时不能互相「满足」。

解法：单调栈维护候选

核心思路

暴力解法是对每个 i 往右扫，找到第一个更大的就停。最坏情况是严格递减数组，每个位置都要扫到末尾，总计 $O(n^2)$。

瓶颈在于大量重复扫描：如果 temperatures[a] <= temperatures[b] 且 a < b，那么当我们从某个位置往右找更大值时，一旦越过了 b，a 就再也不可能是答案的来源——它被 b 完全遮蔽了。换句话说，只有那些「从当前位置往左看、还没有找到更大值」的下标才有资格继续等待，其余的都已经出局。

这批「还在等待」的下标有一个自动成立的性质：它们对应的温度从栈底到栈顶单调不增。因为如果栈里存在一个更靠后却更高的温度，那么它前面那个更低的早就该被它结算掉了。这就是单调栈的由来——不是先决定用单调栈，而是「候选集天然单调」这个事实推出来的。

于是状态定义为：栈里自底向上保存的是下标，它们的温度单调不增，含义是「这些天还没等到更高温度」。

扫描规则：遍历到第 i 天，先看栈顶。只要栈顶那天的温度严格小于今天，说明今天就是它等到的第一个更高温度，弹出并记 answer[j] = i - j；因为栈内单调不增，弹完一个还可能继续满足条件，所以用循环连续结算。当栈顶温度不再小于今天时停止——它还得继续等。最后把今天的下标入栈，它成为新的等待者。

为什么结算的一定是「第一个」更高温度？因为下标 j 是按顺序入栈的，从 j 到 i 之间的每一天都被扫描过，若其中有比 temperatures[j] 更高的，j 早就在那时被弹出了。所以 i 必然是 j 之后第一个更高的日子。

结果数组初始化为全 0，扫描结束后仍留在栈里的下标就是「之后再无更高温度」的那些，它们的答案保持默认的 0，不需要任何额外收尾。

解题步骤

  • 初始化结果数组：int[] answer = new int[n]，Java 与 Go 的整型数组默认全 0，正好对应「等不到更高温度」的语义，省掉最后一遍填充。
  • 栈里存下标而不是温度：只有下标才能同时算距离（i - j）和查温度（temperatures[j]）；存温度会丢失位置信息，无法计算答案。
  • 弹栈条件用严格小于：while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i])。用 < 而不是 <=，是因为题目要求严格更高的温度；写成 <= 会让相同温度互相结算，[70, 70] 会错误地得到 [1, 0]。
  • 弹栈时立即写答案：int j = stk.pop(); answer[j] = i - j;。这一步必须在弹出的同时完成，因为 j 一旦离开栈就再无机会被结算。
  • 循环连续结算：栈内单调不增，今天可能一口气结算掉多个等待者，所以用 while 而非 if。
  • 今天入栈：stk.push(i)。无论有没有结算过别人，今天自己都要成为新的等待者。
  • 无需收尾：残留在栈中的下标其答案保持初始的 0。

以 temperatures = [73, 74, 75, 71, 69, 72, 76, 73] 走一遍，栈中记录下标。

i=0（73）：栈空，直接入栈，栈为 [0]。i=1（74）：栈顶下标 0 的温度 73 严格小于 74，弹出并记 answer[0] = 1 - 0 = 1；栈空，1 入栈，栈为 [1]。i=2（75）：栈顶温度 74 < 75，弹出记 answer[1] = 2 - 1 = 1；栈空后 2 入栈，栈为 [2]。

i=3（71）：栈顶温度 75 不小于 71，不结算，3 入栈，栈为 [2, 3]。i=4（69）：栈顶温度 71 不小于 69，4 入栈，栈为 [2, 3, 4]——注意此刻栈内温度是 75、71、69，确实单调不增。

i=5（72）：栈顶下标 4 的温度 69 < 72，弹出记 answer[4] = 5 - 4 = 1；新栈顶下标 3 的温度 71 < 72，弹出记 answer[3] = 5 - 3 = 2；再看栈顶下标 2 的温度 75，不小于 72，停止；5 入栈，栈为 [2, 5]。这一轮连续结算了两个，正是 while 的价值。

i=6（76）：栈顶下标 5 的温度 72 < 76，弹出记 answer[5] = 6 - 5 = 1；栈顶下标 2 的温度 75 < 76，弹出记 answer[2] = 6 - 2 = 4；栈空，6 入栈，栈为 [6]。i=7（73）：栈顶温度 76 不小于 73，7 入栈，栈为 [6, 7]。

扫描结束，栈里还剩下标 6 和 7，它们的答案保持初始值 0。最终 answer = [1, 1, 4, 2, 1, 1, 0, 0]，与预期一致。

再看相等温度的用例 [70, 70, 71]：i=0 入栈；i=1 时栈顶温度 70 不严格小于 70，不结算，1 入栈，栈为 [0, 1]；i=2 时栈顶下标 1 的温度 70 < 71，弹出记 answer[1] = 1，栈顶下标 0 的温度 70 < 71，弹出记 answer[0] = 2。最终 [2, 1, 0]，正确——若弹栈条件写成 <=，第 0 天会被第 1 天错误结算成 1。

代码实现

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        // 默认全 0，正好对应「之后再无更高温度」。
        int[] answer = new int[n];
        // 栈里存下标，温度自底向上单调不增，含义是「还没等到更高温度的日子」。
        Deque<Integer> stk = new ArrayDeque<>();
        for (int i = 0; i < n; ++i) {
            // 严格小于才结算，相同温度不算「更高」。
            while (!stk.isEmpty() && temperatures[stk.peek()] < temperatures[i]) {
                int j = stk.pop();
                answer[j] = i - j;
            }
            stk.push(i);
        }
        return answer;
    }
}

func dailyTemperatures(temperatures []int) []int {
    // 默认全 0，正好对应「之后再无更高温度」。
    answer := make([]int, len(temperatures))
    // 栈里存下标，温度自底向上单调不增。
    var stk []int
    for i, t := range temperatures {
        // 严格小于才结算，相同温度不算「更高」。
        for len(stk) > 0 && temperatures[stk[len(stk)-1]] < t {
            j := stk[len(stk)-1]
            answer[j] = i - j
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, i)
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$。每个下标最多入栈一次、出栈一次，内层 while 的总弹栈次数被入栈总数限制住，所以虽然有嵌套循环，整体仍是线性的均摊代价，而不是 $O(n^2)$。
  • 空间复杂度：$O(n)$，来自单调栈。最坏情况是严格递减数组（如 [5,4,3,2,1]），没有任何元素被结算，所有下标都堆在栈里。返回的结果数组是必需输出，不计入额外空间。

关键点总结

  • 「找右边第一个更大的元素」是单调栈的标准场景，识别出这个形态后，写法就是固定的模板；本题只是把返回值从元素换成了下标差。
  • 单调性不是人为规定的，而是「被更大元素遮蔽的候选自动出局」推导出来的结果，理解这条推导才能在变形题里自己写出正确的弹栈条件。
  • 栈里存下标而不是值，是这类题的通用选择：下标能反查值，值却反查不了下标，凡是答案与位置有关就必须存下标。
  • 弹栈条件里的严格与非严格，直接对应题目中的「更大」还是「不小于」，处理重复元素时必须逐字核对题面。
  • 结果数组用默认值 0 承载「无解」语义，省掉扫描结束后清空栈的收尾代码，这类「让默认值恰好等于兜底答案」的技巧值得刻意留意。
  • 面试视角：先讲 $O(n^2)$ 暴力并指出重复扫描的浪费，再引出「谁还有资格当候选」的分析，最后给出均摊 $O(n)$ 的证明。面试官常追问「如果数组是环形的怎么办」，答案是把数组遍历两遍（下标取模）而栈只在第一遍入栈，这正是 503 题。

易错点总结

  • 弹栈条件写成 <=：[70, 70, 71] 中第 1 天会把第 0 天结算成 1，正确答案应是 2。
  • 栈里存温度而不是下标：弹栈时算不出 i - j 的距离，只能得到温度值，答案完全无法构造。
  • 用 if 而不是 while 结算：[75, 71, 69, 72] 中处理 72 时只结算掉 69，71 被漏掉，答案里 71 那一位错成 0。
  • 弹栈后忘记写 answer[j]：元素离开栈就永远不会再被处理，对应位置保持 0，[73, 74] 会输出 [0, 0]。
  • 先入栈再结算：把 stk.push(i) 写在 while 之前，今天会与自己比较，temperatures[i] < temperatures[i] 恒为假虽然不会立刻出错，但一旦条件是 <= 就会自我结算出 0，逻辑彻底混乱。
  • 答案写成 j - i 或 i - j - 1：[73, 74] 会得到 -1 或 0，正确答案是 1；距离的定义是「等待的天数」，即两个下标之差。
  • 扫描结束后遍历栈把答案填成别的值：残留元素的答案就该是 0，额外填充反而会覆盖正确结果。
  • 忘记判空就取栈顶：数组首个元素处理时栈为空，直接 peek 会返回空值或抛异常。
  • 两重循环暴力求解：[100000, 99999, ..., 1] 这类严格递减的十万级输入会跑到平方级，直接超时。

相似题目

题目 难度 考察点
739. 每日温度 中等 与本题同题，可直接套用单调栈模板
496. 下一个更大元素 I 简单 返回的是元素值而非距离，且要先对主数组建好映射再按子集查询
503. 下一个更大元素 II 中等 数组是环形的，需遍历两遍并对下标取模，第二遍只结算不入栈
1019. 链表中的下一个更大节点 中等 载体换成链表，需先转成数组或边遍历边维护栈中的位置
901. 股票价格跨度 中等 方向反过来找左边更大的元素，且要求在线处理而非一次性给出全部数据
84. 柱状图中最大的矩形 困难 需要同时求左右两侧第一个更小的位置，再由宽高相乘取最大值
42. 接雨水 困难 弹栈时结算的是横向的凹槽面积，需要同时用到栈顶、新栈顶与当前柱子