LeetCode 739. 每日温度

约 4 分钟
文章信息 19 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 历史考题 50-100 LeetCode 75 LeetCode 热题 100 腾讯 字节 华为 微软 美团 拼多多 滴滴 B站 虾皮 作业帮
标签
数组 栈 单调栈

题目描述

✅ 739. 每日温度

image-20260928194054785

题意分析

对每一天，找到它之后第一个温度严格更高的日期，返回需要等待的天数，也就是两个日期的下标差。不是求温度差，也不是随便找一个更暖的日期。

温度相同不能结束等待；如果后面始终没有更暖的一天，这一天的答案为 0。结果数组与输入等长，每个位置分别对应原来的那一天。

解法：单调栈保存未匹配日期

核心思路

[!blue]

如果从每一天向后逐个寻找，会反复扫描同一段温度。可以反过来考虑：从左到右遇到一个新温度时，它能为之前哪些还在等待的日期确定答案？

用栈保存尚未找到更暖日期的下标，栈底到栈顶的下标递增，对应温度非递增。当前温度高于栈顶时，栈顶日期已经等到了更暖的一天，弹出它，并用当前下标减去旧下标得到等待天数。当前温度还可能高于弹出后的新栈顶，所以要持续检查。

当前日期为什么一定是旧日期之后的第一个更暖日？因为日期按顺序扫描，旧日期一直留在栈中，说明此前没有更暖日为它完成匹配；如今第一次被弹出，就恰好遇到了最近的更暖日。

弹栈停止时，栈为空，或者栈顶温度不低于当前温度。后一种情况下，栈中更下面的温度也不低于栈顶，当前日不可能再解决它们，因此可以停止检查。随后把当前下标入栈，温度的非递增关系仍然成立。扫描结束还留在栈中的日期没有更暖日，保留初始答案 0。

解题步骤

  1. 创建长度为 n、初值全为 0 的结果数组，以及保存日期下标的空栈。
  2. 从左到右扫描当前下标 i，比较 temperatures[i] 与栈顶下标对应的温度。
  3. 只要当前温度严格更高，就弹出 prev，写入 res[prev] = i - prev，再检查新的栈顶。
  4. 无法继续弹栈时，将当前下标 i 入栈，等待后面更暖的日期。
  5. 扫描结束返回结果，未弹出的日期无需额外处理。

代码实现

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < temperatures.length; i++) {
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int prev = stack.pop();

                // 当前日期是 prev 之后第一个更高温度日期。
                res[prev] = i - prev;
            }

            stack.push(i);
        }

        return res;
    }
}

func dailyTemperatures(temperatures []int) []int {
    res := make([]int, len(temperatures))
    stack := make([]int, 0)

    for i := 0; i < len(temperatures); i++ {
        for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {
            prev := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 当前下标为 prev 找到第一个更高温度。
            res[prev] = i - prev
        }
        stack = append(stack, i)
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$。每个下标恰好入栈一次、至多出栈一次，全部日期的弹栈总次数不超过 $n$；嵌套循环不会让同一下标被重复扫描多次。
  • 空间复杂度：$O(n)$。温度始终不升时，所有日期都可能留在栈中；不计返回结果数组本身的空间。

关键点总结

[!green]

  • 栈保存未得到答案的日期下标，既能回查温度，也能计算等待天数。
  • 弹栈意味着该日期第一次遇到更暖日，答案可以立即确定，之后无需再参与比较。
  • 相等温度保留在栈中，弹栈条件必须是严格大于。
  • 一个当前温度可能同时解决多个旧日期，因此弹栈使用循环。

易错点总结

[!yellow]

  • 把弹栈条件写成 >=，会把同温度的日期误当作更暖日。
  • 只用一次 if 弹栈，当前温度可能已经足够解决更深的多个日期，却没有继续更新它们。
  • 栈中只存温度，无法区分相同温度出现的位置，也无法得到等待天数。
  • 将答案写成温度之差，或者给当前下标写答案；此时确定的是旧下标 prev 的下标距离 i - prev。
  • 给最终留在栈中的日期填 -1，与题目要求不符；默认的 0 就是它们的答案。

相似题目

题目 难度 关联与区别
496. 下一个更大元素 I 简单 同样寻找右侧第一个更大元素，本题返回距离，所以栈中保存下标。
503. 下一个更大元素 II 中等 原题数组首尾相接，需要再次扫描来补足跨边界的更大值，本题只向右查找。
1019. 链表中的下一个更大节点 中等 用单调栈确定最近的更大元素；本题返回右侧更大值的下标距离，该题先把链表值转为顺序序列处理。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/19856294
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！