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

题目描述

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

示例：

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

解题思路分析

暴力解法（不可行）

最直观的想法是对于每一天，向后遍历找到第一个比当前温度高的日子。这种方法时间复杂度为 O(n²)，在数据量大时会超时。

更优解法：单调栈

我们可以使用单调递减栈来高效解决这个问题。栈中存储的是日期索引，而不是温度值本身，这样我们可以通过索引访问温度。

详细解题步骤

步骤1：理解单调栈的作用

• 维护一个栈，栈中的索引对应的温度是单调递减的
• 当我们遍历到某一天时，如果这天的温度比栈顶那天的温度高，说明我们找到了栈顶那天对应的"更暖和的日子"
• 这样就可以一次性处理栈中所有比当前温度低的日子

步骤2：具体算法流程

1. 初始化一个空栈和一个全零的结果数组
2. 遍历每一天的温度：
   • 当栈不为空且当前温度 > 栈顶那天的温度时：
     • 弹出栈顶元素（这是找到更暖和日子的那天）
     • 计算等待天数 = 当前天数索引 - 栈顶那天索引
     • 将等待天数存入结果数组对应位置
   • 将当前天数索引入栈
3. 遍历结束后，栈中剩余的天数对应的结果保持为0（因为没有更暖和的日子）

步骤3：示例推演

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

天数: 0   1   2   3   4   5   6   7
温度: 73, 74, 75, 71, 69, 72, 76, 73

遍历过程：

• 第0天(73)：栈空，索引入栈 → stack = [0]
• 第1天(74)：74 > 73（栈顶第0天），弹出0，answer[0] = 1-0 = 1，索引入栈 → stack = [1]
• 第2天(75)：75 > 74（栈顶第1天），弹出1，answer[1] = 2-1 = 1，索引入栈 → stack = [2]
• 第3天(71)：71 < 75（栈顶第2天），索引入栈 → stack = [2,3]
• 第4天(69)：69 < 71（栈顶第3天），索引入栈 → stack = [2,3,4]
• 第5天(72)：72 > 69（栈顶第4天），弹出4，answer[4] = 5-4 = 1
  72 > 71（新栈顶第3天），弹出3，answer[3] = 5-3 = 2
  72 < 75（新栈顶第2天），索引入栈 → stack = [2,5]
• 第6天(76)：76 > 72（栈顶第5天），弹出5，answer[5] = 6-5 = 1
  76 > 75（新栈顶第2天），弹出2，answer[2] = 6-2 = 4，索引入栈 → stack = [6]
• 第7天(73)：73 < 76（栈顶第6天），索引入栈 → stack = [6,7]

最终结果：[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. 每次遇到更高温度时，可以一次性处理栈中所有比当前温度低的日子

这种单调栈的思路在很多"下一个更大元素"类问题中都有应用，是重要的算法技巧。