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]

解题过程

这个问题的核心是，对于数组中的每一个元素，我们需要找到它右边第一个比它大的元素，并计算两者之间的距离。这类“寻找下一个更大元素”的问题，通常可以使用单调栈来高效解决。

1. 暴力解法（理解问题）

最直观的方法是使用双重循环：

• 对于每一天 i，我们从 i+1 开始向后遍历。
• 找到第一个温度高于 temperatures[i] 的天 j。
• 那么 answer[i] = j - i。
• 如果遍历到最后都找不到，则 answer[i] = 0。

这种方法的时间复杂度是 O(n²)，在数据量大的时候会超时。我们需要一种更高效的方法。

2. 单调栈解法思路

单调栈的核心思想是维护一个栈，栈内的元素（这里我们存储数组的索引）对应的温度值是单调递减的。

• 我们按顺序遍历每一天的温度。
• 对于当前天 i 的温度，我们将其与栈顶元素 stack[top] 那天的温度进行比较。
• 如果当前温度更高，说明对于栈顶那天的温度而言，当前天 i 就是它右边第一个更温暖的日子。这时我们就可以计算出结果，并将栈顶元素弹出。
• 重复这个过程，直到当前温度不再高于栈顶那天的温度（或栈为空），然后将当前天 i 的索引入栈。

这样，栈内保存的始终是那些“尚未找到更温暖日子”的天的索引，并且这些天的温度是递减的，所以栈是“单调”的。

3. 逐步推演

我们以示例 [73,74,75,71,69,72,76,73] 来一步步推演：

• 初始化：answer = [0,0,0,0,0,0,0,0]，栈 stack 为空。
• i=0 (73)：栈为空，将索引0入栈。stack = [0]
• i=1 (74)：当前温度74 > 栈顶索引0的温度73。找到了！
• 弹出栈顶索引0，计算 answer[0] = 1 - 0 = 1。
• 现在栈为空，将索引1入栈。stack = [1]
• i=2 (75)：当前温度75 > 栈顶索引1的温度74。找到了！
• 弹出栈顶索引1，计算 answer[1] = 2 - 1 = 1。
• 栈为空，将索引2入栈。stack = [2]
• i=3 (71)：当前温度71 <= 栈顶索引2的温度75。不弹出，将索引3入栈。stack = [2, 3]
• i=4 (69)：当前温度69 <= 栈顶索引3的温度71。不弹出，将索引4入栈。stack = [2, 3, 4]
• i=5 (72)：当前温度72 > 栈顶索引4的温度69。找到了！
• 弹出栈顶索引4，计算 answer[4] = 5 - 4 = 1。
• 现在栈顶是索引3（温度71），当前温度72 > 71。继续弹出！
• 弹出栈顶索引3，计算 answer[3] = 5 - 3 = 2。
• 现在栈顶是索引2（温度75），当前温度72 <= 75。停止比较。
• 将索引5入栈。stack = [2, 5]
• i=6 (76)：当前温度76 > 栈顶索引5的温度72。找到了！
• 弹出栈顶索引5，计算 answer[5] = 6 - 5 = 1。
• 现在栈顶是索引2（温度75），当前温度76 > 75。继续弹出！
• 弹出栈顶索引2，计算 answer[2] = 6 - 2 = 4。
• 栈为空，将索引6入栈。stack = [6]
• i=7 (73)：当前温度73 <= 栈顶索引6的温度76。不弹出，将索引7入栈。stack = [6, 7]
• 遍历结束。栈中剩余的索引 [6, 7] 代表它们之后没有更温暖的日子，根据初始化，它们的 answer 值已经是0。

最终得到结果：answer = [1,1,4,2,1,1,0,0]。

4. 代码实现（Python）

def dailyTemperatures(temperatures):
    n = len(temperatures)
    answer = [0] * n  # 初始化结果数组，默认值为0
    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。

这种方法巧妙地利用了栈的“后进先出”特性，将寻找“下一个更大元素”的过程优化到了线性时间复杂度。