739. 每日温度 (Medium)

专题归类： 06-栈与堆 LeetCode 链接： https://leetcode.cn/problems/daily-temperatures/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1：

输入：temperatures = [73,74,75,71,69,72,76,73]
输出：[1,1,4,2,1,1,0,0]

示例 2：

输入：temperatures = [30,40,50,60]
输出：[1,1,1,0]

示例 3：

输入：temperatures = [30,60,90]
输出：[1,1,0]

---

题目详细分析

• 数据范围： 1 ≤ temperatures.length ≤ 10^5，30 ≤ temperatures[i] ≤ 100。数组长度可达 10 万，O(n²) 的双重循环会超时。
• 输入输出特征： 输入整数数组表示温度，输出整数数组表示等待天数。当天数不足 1 天（没有更高温度）时填 0。
• 边界条件：
  • 数组长度为 1 → 直接返回 [0]。
  • 温度递减序列 → 全部为 0。
  • 温度递增序列 → 全部为 1（最后一天为 0）。
• 核心约束： 需要在 O(n) 时间内解决。暴力法是 O(n²)，对于 10^5 的数据规模不可行。
• 隐藏条件：
  • 本质是找数组中每个元素 右边第一个比它大的元素 的距离（不是值，是索引差）。
  • 单调栈是解决这类「下一个更大元素」问题的标准利器。
  • 栈中存的是 索引 而非温度值，因为需要计算天数差。

---

小白版直白理解

就像你在等一个更暖和的日子。你每天看天气预报，想知道：从今天起，还要等多少天才能遇到一个比今天更暖和的日子？

如果气温一直下降，那你就永远等不到（填 0）。

单调栈的思路：想象你有一叠 未解决的日子的纸条，纸条上写着那天的温度。每天拿到新的温度时，就把这叠纸条从顶部开始翻看——凡是温度比今天低的纸条，都可以解决了（它们等到了更暖的天），计算天数差，然后扔掉。最后把今天的温度放到最上面。

这样每张纸条只被放入和取出一次，所以效率很高。

---

解题思路

思路一：单调递减栈（推荐）

核心思想： 维护一个单调递减栈（栈底 → 栈顶，温度越来越低）。遍历温度数组，当当前温度 > 栈顶温度时，说明栈顶温度遇到了右边第一个更高的温度，弹栈并计算结果。

为什么用栈？因为温度数组是按时间顺序的，后面的温度对前面的温度的影响是「后进先出」的——后面的低温先遇到后面的高温而解决，前面的低温要等更久。

def dailyTemperatures(temperatures):
    n = len(temperatures)
    res = [0] * n       # 初始化结果数组
    stack = []          # 存储索引，栈底→栈顶：温度递减
 
    for i in range(n):
        # 当前温度比栈顶温度高 → 栈顶遇到了右边第一个更高温度
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            res[idx] = i - idx    # 天数差
        stack.append(i)            # 当前索引入栈
 
    return res

复杂度： 时间 O(n)（每个元素最多入栈一次、出栈一次），空间 O(n)

思路二：暴力法（提供对比）

从每个位置出发向后遍历找第一个更高温度，O(n²) 超时但思路直观。

def dailyTemperatures(temperatures):
    n = len(temperatures)
    res = [0] * n
    for i in range(n):
        for j in range(i + 1, n):
            if temperatures[j] > temperatures[i]:
                res[i] = j - i
                break
    return res

思路三：从右向左遍历 + 跳跃优化

从右向左遍历，利用已经计算过的结果跳跃查找，平均 O(n)。

def dailyTemperatures(temperatures):
    n = len(temperatures)
    res = [0] * n
    for i in range(n - 2, -1, -1):
        j = i + 1
        while j < n:
            if temperatures[j] > temperatures[i]:
                res[i] = j - i
                break
            elif res[j] == 0:
                break
            else:
                j += res[j]  # 跳跃到更高温度的位置
    return res

思路： 如果 temperatures[j] <= temperatures[i]，那就先跳到比 j 更高温度的位置 j + res[j]，因为中间的温度都 ≤ temperatures[j] ≤ temperatures[i]，没必要逐一比较。

---

易错点

• 栈中存索引不是值： 单调栈需要计算天数差（索引差值），所以栈中必须存索引。如果存温度值，就无法计算距离。
• 单调性方向： 本题找「下一个更高温度」，维护的是 单调递减栈（栈底到栈顶递减）。如果找「下一个更小元素」则维护单调递增栈。保持方向正确很重要。
• while 条件： temperatures[stack[-1]] < temperatures[i] 用 < 还是 <=？本题严格大于才能算更高温度，相等不算，所以用 <。
• 结果数组初始化： 所有位置默认值为 0，这样遇到没有更高温度的天数不需要额外处理。
• 连续相等值： [30, 30, 40]，第 0 天和第 1 天温度相等，第 0 天要等到第 2 天（40），所以第 0 天的结果是 2。相等时不弹栈，因为相等不算更高温度。

---

框架提炼

单调栈模板（找右边第一个更大元素）：

def next_greater_element(nums):
    """返回每个元素右边第一个比它大的元素的索引差（或值）"""
    n = len(nums)
    res = [0] * n       # 默认值
    stack = []          # 单调递减栈，存索引
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            res[idx] = i - idx       # 或 nums[i]（如果返回值）
        stack.append(i)
    
    return res

单调栈的变体：

目标	栈单调性	比较符号
右边第一个更大	递减	<
右边第一个更小	递增	>
左边第一个更大	递减（倒序遍历）	<
左边第一个更小	递增（倒序遍历）	>

---

关联题目

• 84-柱状图中最大的矩形 — 单调栈的经典进阶题。739 是找下一个更大元素，84 是利用单调栈找左右边界来计算面积。
• 496-下一个更大元素 I — 一模一样的单调栈思想，但多了一层哈希表映射。
• 42-接雨水 — 可以使用单调栈（递减栈）求解，与 739 一样都是栈中存索引，在出栈时计算结果。