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]

1. 问题理解与思路分析
这个问题的核心是：对于数组中的每个元素，需要找到它右边第一个比它大的元素，并计算两者下标的差值。如果没有更大的元素，结果记为 0。

一种直观的暴力解法是：对于每一天 i，向后扫描直到找到第一个温度更高的日子 j，然后 answer[i] = j - i。但这种方法的时间复杂度是 O(n²)，在数据量大时效率很低。

我们需要一种更高效的方法。观察发现，当我们遍历数组时，有些天的温度可能暂时找不到更高的，但后续某天的温度可能会同时成为前面多个低温天的“下一个更高温度”。这种“等待匹配”的特性提示我们可以使用单调栈（Monotonic Stack）来优化。

2. 单调栈解法思路
单调栈是维护栈内元素单调性的一种数据结构。在这里，我们维护一个单调递减栈（从栈底到栈顶温度递减），栈中存放的是日期（下标）。

• 当我们遍历到一个新的温度时，将其与栈顶的温度比较。
• 如果当前温度 ≤ 栈顶温度，说明栈顶那天的“下一个更高温度”还没到来，将当前日期入栈。
• 如果当前温度 > 栈顶温度，说明当前温度就是栈顶那天的“下一个更高温度”，我们可以计算差值并记录结果，然后弹出栈顶。接着继续与新的栈顶比较，直到当前温度 ≤ 栈顶温度或栈为空。

3. 详细步骤演示
以 temperatures = [73,74,75,71,69,72,76,73] 为例：

• 初始化：栈 stack = []，结果数组 answer = [0,0,0,0,0,0,0,0]
• 第 0 天（温度 73）：栈空，入栈。stack = [0]
• 第 1 天（温度 74）：74 > 73（栈顶温度），所以第 0 天的答案 = 1 - 0 = 1。弹出 0，栈空后入栈 1。stack = [1]，answer = [1,0,0,0,0,0,0,0]
• 第 2 天（温度 75）：75 > 74，第 1 天的答案 = 2 - 1 = 1。弹出 1，栈空后入栈 2。stack = [2]，answer = [1,1,0,0,0,0,0,0]
• 第 3 天（温度 71）：71 ≤ 75，入栈。stack = [2,3]
• 第 4 天（温度 69）：69 ≤ 71，入栈。stack = [2,3,4]
• 第 5 天（温度 72）：72 > 69（栈顶温度），第 4 天的答案 = 5 - 4 = 1。弹出 4。现在栈顶是 3（温度 71），72 > 71，第 3 天的答案 = 5 - 3 = 2。弹出 3。现在栈顶是 2（温度 75），72 ≤ 75，入栈 5。stack = [2,5]，answer = [1,1,0,2,1,0,0,0]
• 第 6 天（温度 76）：76 > 72（栈顶温度），第 5 天的答案 = 6 - 5 = 1。弹出 5。现在栈顶是 2（温度 75），76 > 75，第 2 天的答案 = 6 - 2 = 4。弹出 2，栈空后入栈 6。stack = [6]，answer = [1,1,4,2,1,1,0,0]
• 第 7 天（温度 73）：73 ≤ 76，入栈。stack = [6,7]
• 遍历结束，栈中剩余的天数（第 6、7 天）右边没有更高温度，答案保持为 0。

最终结果：[1,1,4,2,1,1,0,0]

4. 代码实现

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

5. 复杂度分析

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

6. 关键点总结

• 使用单调递减栈来跟踪“尚未找到更高温度”的日期。
• 当遇到更高温度时，它可能是栈中多个日期的“下一个更高温度”，需要逐个处理。
• 这种方法避免了重复比较，将时间复杂度从 O(n²) 优化到 O(n)。