我来给你讲解 LeetCode 第 739 题「每日温度」。

题目描述

给定一个整数数组 temperatures，表示每天的温度。你需要返回一个数组 answer，其中 answer[i] 是指对于第 i 天，要等至少多少天才能出现比当天温度更高的温度。如果未来没有更高温度，则 answer[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. 暴力解法（会超时）

对于每一天 i，向后遍历找到第一个 j 使得 temperatures[j] > temperatures[i]，则 answer[i] = j - i。
时间复杂度：O(n²)，空间复杂度：O(1)（不包含输出数组）。

这种方法在数据量大时效率很低。

2. 更优解法：单调栈

核心思想

我们维护一个栈，栈里存放的是温度的索引（而不是温度值本身），并且保证栈中索引对应的温度是单调递减的（从栈底到栈顶温度递减）。

遍历每一天的温度：

• 如果当前温度 ≤ 栈顶那天的温度，就把当前索引入栈（因为还没找到更高温度）。
• 如果当前温度 > 栈顶那天的温度，说明栈顶那天等到了更高温度，我们就计算天数差，并更新答案，然后弹出栈顶（因为已经找到答案），继续与新的栈顶比较，直到栈为空或当前温度 ≤ 栈顶温度。

这样，每个索引最多入栈一次、出栈一次，时间复杂度 O(n)。

逐步推演示例

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

初始化：stack = [], answer = [0,0,0,0,0,0,0,0]

1. i=0, 温度 73
   栈空 → 入栈 [0]

2. i=1, 温度 74
   74 > 73（栈顶 0 对应温度 73） → 计算 answer[0] = 1 - 0 = 1，弹出 0
   栈空 → 入栈 [1]

3. i=2, 温度 75
   75 > 74（栈顶 1 对应温度 74） → answer[1] = 2 - 1 = 1，弹出 1
   栈空 → 入栈 [2]

4. i=3, 温度 71
   71 ≤ 75（栈顶 2 对应温度 75） → 入栈 [2, 3]

5. i=4, 温度 69
   69 ≤ 71 → 入栈 [2, 3, 4]

6. i=5, 温度 72
   72 > 69（栈顶 4 对应温度 69） → answer[4] = 5 - 4 = 1，弹出 4
   72 > 71（栈顶 3 对应温度 71） → answer[3] = 5 - 3 = 2，弹出 3
   72 ≤ 75 → 入栈 [2, 5]

7. i=6, 温度 76
   76 > 72（栈顶 5 对应温度 72） → answer[5] = 6 - 5 = 1，弹出 5
   76 > 75（栈顶 2 对应温度 75） → answer[2] = 6 - 2 = 4，弹出 2
   栈空 → 入栈 [6]

8. i=7, 温度 73
   73 ≤ 76 → 入栈 [6, 7]

遍历结束，栈中剩余索引对应的天数答案为 0（已初始化）。

最终 answer = [1, 1, 4, 2, 1, 1, 0, 0]。

3. 代码实现（Python）

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n
    stack = []  # 存储索引
    
    for i in range(n):
        # 当栈不为空且当前温度大于栈顶索引对应的温度
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            answer[idx] = i - idx
        stack.append(i)
    
    return answer

4. 复杂度分析

• 时间复杂度：O(n)，每个索引最多入栈、出栈一次。
• 空间复杂度：O(n)，最坏情况下栈的大小为 n。

总结

这道题是单调栈的经典应用，用来解决“下一个更大元素”类的问题。
关键点：

• 栈中存索引，便于计算天数差。
• 栈内温度单调递减，遇到更高温度时依次弹出并计算答案。