leetcode-每日温度

每日温度

给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 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 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

暴力解法 O(N^2)

暴力解法主要是使用两层循环。对于每一天，向后遍历找到第一个比它温度高的日子。

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        # 外层遍历每一个元素
        for i in range(n):
            # 内层寻找第一个比当前温度高的
            for j in range(i + 1, n):
                if temperatures[j] > temperatures[i]:
                    result[i] = j - i
                    break
        return result

复杂度分析

• 时间复杂度：$O(N^2)$。在最坏情况下（例如数组递减），内层循环几乎每次都要遍历剩余所有元素。由于题目提示 $N$ 可达 $10^5$，这个解法会超时。
• 空间复杂度：$O(1)$。除了返回的数组外，不需要额外的空间。

单调栈 O(N)

这道题本质上是寻找数组中右边第一个比当前元素大的元素。这是单调栈的典型应用场景。

核心思路：

维护一个存储下标的栈，栈内的元素对应的温度是单调递减的。

1. 遍历数组 temperatures。
2. 如果栈不为空，且当前温度 current_temp 大于栈顶下标对应的温度，说明栈顶元素的下一个更高温度就是当前元素。
   • 弹出栈顶下标 prev_index。
   • 计算距离 i - prev_index 并存入结果数组。
   • 重复上述过程，直到栈为空或当前温度不大于栈顶温度。
3. 将当前下标 i 入栈（因为此时它可能还没有找到下一个更高温度）。

适用场景：

单调栈适合解决以下类型的问题：

• 寻找右边第一个更大元素
• 寻找右边第一个更小元素
• 寻找左边第一个更大元素
• 寻找左边第一个更小元素

代码实现：

from typing import List

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        result = [0] * n
        stack = []  # 存储下标

        for i, temp in enumerate(temperatures):
            # 当栈不为空，且当前温度大于栈顶下标对应的温度
            while stack and temp > temperatures[stack[-1]]:
                prev_index = stack.pop()
                # 计算距离：当前位置 - 栈顶元素位置
                result[prev_index] = i - prev_index
            
            # 无论如何，将当前下标入栈
            stack.append(i)

        return result

复杂度分析

• 时间复杂度：$O(N)$。虽然有 while 循环，但每个元素的下标最多进栈一次、出栈一次。
• 空间复杂度：$O(N)$。最坏情况下（例如数组递减），栈中需要存储所有元素的下标。