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

题目描述

给定一个整数数组 temperatures，表示每天的温度。你需要返回一个数组 answer，其中 answer[i] 是指在第 i 天之后，要等多少天才能遇到一个更暖和的温度。如果未来没有更暖和的天气，则用 0 代替。

示例：

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

解题思路分析

暴力解法（不可行）

最直观的想法是：对于每一天 i，向后遍历找到第一个比 temperatures[i] 大的温度。

• 时间复杂度：O(n²)，会超时
• 空间复杂度：O(1)

我们需要更高效的算法。

单调栈解法

核心思想：维护一个栈，栈中存放的是尚未找到更暖温度的日期的索引。栈中的索引对应的温度值是单调递减的。

算法步骤：

1. 初始化一个空栈和一个全零的结果数组
2. 遍历每一天的温度：
   • 当栈不为空且当前温度大于栈顶那天的温度时：
     • 弹出栈顶元素（找到了更暖的温度）
     • 计算天数差 = 当前索引 - 栈顶索引
     • 将结果存入对应位置
   • 将当前索引入栈
3. 返回结果数组

详细步骤演示

以示例 [73,74,75,71,69,72,76,73] 为例：

第0天（温度73）：

• 栈为空，直接入栈：stack = [0]
• answer = [0,0,0,0,0,0,0,0]

第1天（温度74）：

• 74 > 73（栈顶第0天的温度）：
  • 弹出第0天，计算：answer[0] = 1 - 0 = 1
  • 栈变空
• 第1天入栈：stack = [1]
• answer = [1,0,0,0,0,0,0,0]

第2天（温度75）：

• 75 > 74（栈顶第1天的温度）：
  • 弹出第1天，计算：answer[1] = 2 - 1 = 1
  • 栈变空
• 第2天入栈：stack = [2]
• answer = [1,1,0,0,0,0,0,0]

第3天（温度71）：

• 71 ≤ 75（栈顶第2天的温度），直接入栈：stack = [2,3]
• answer = [1,1,0,0,0,0,0,0]

第4天（温度69）：

• 69 ≤ 71（栈顶第3天的温度），直接入栈：stack = [2,3,4]
• answer = [1,1,0,0,0,0,0,0]

第5天（温度72）：

• 72 > 69（栈顶第4天的温度）：
  • 弹出第4天，计算：answer[4] = 5 - 4 = 1
  • stack = [2,3]
• 72 > 71（栈顶第3天的温度）：
  • 弹出第3天，计算：answer[3] = 5 - 3 = 2
  • stack = [2]
• 72 ≤ 75，第5天入栈：stack = [2,5]
• answer = [1,1,0,2,1,0,0,0]

第6天（温度76）：

• 76 > 72（栈顶第5天的温度）：
  • 弹出第5天，计算：answer[5] = 6 - 5 = 1
  • stack = [2]
• 76 > 75（栈顶第2天的温度）：
  • 弹出第2天，计算：answer[2] = 6 - 2 = 4
  • 栈变空
• 第6天入栈：stack = [6]
• answer = [1,1,4,2,1,1,0,0]

第7天（温度73）：

• 73 ≤ 76，直接入栈：stack = [6,7]
• answer = [1,1,4,2,1,1,0,0]

代码实现

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

复杂度分析

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

关键理解点

1. 单调栈：栈中温度保持递减顺序，确保我们总能找到"第一个"更暖的温度
2. 索引存储：栈中存储索引而不是温度值，方便计算天数差
3. 延迟计算：对于暂时找不到更暖温度的日子，先压入栈中等待后续处理

这种解法巧妙地利用了栈的LIFO特性，高效地解决了"找下一个更大元素"的问题。