LeetCode 热题 100 | 739. 每日温度
大家好，今天我们来解决一道经典的算法题——每日温度。这道题在 LeetCode 上被标记为中等难度，要求我们找到一个数组，其中每个元素表示从当前天开始，下一个更高温度出现的天数。如果之后没有更高的温度，则用 0 代替。下面我将详细讲解解题思路，并附上 Python 代码实现。
问题描述
给定一个整数数组 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]
解题思路
核心思想
-
单调栈：
- 使用一个栈来存储温度的索引，栈内元素保持单调递减的顺序。
- 遍历温度数组时，如果当前温度大于栈顶温度，说明找到了一个更高的温度，可以更新答案并弹出栈顶元素。
- 如果当前温度小于或等于栈顶温度，直接将当前索引入栈。
-
答案数组初始化：
- 初始化答案数组
answer，长度与temperatures相同，所有元素初始值为0。如果后续没有找到更高的温度，这些位置的值将保持为0。
- 初始化答案数组
Python代码实现
def dailyTemperatures(temperatures):n = len(temperatures)answer = [0] * n # 初始化答案数组stack = [] # 单调栈，存储温度的索引for i, temp in enumerate(temperatures):# 当前温度大于栈顶温度，更新答案并弹出栈顶元素while stack and temp > temperatures[stack[-1]]:prev_index = stack.pop()answer[prev_index] = i - prev_index# 当前索引入栈stack.append(i)return answer# 测试示例
print(dailyTemperatures([73,74,75,71,69,72,76,73])) # 输出: [1,1,4,2,1,1,0,0]
print(dailyTemperatures([30,40,50,60])) # 输出: [1,1,1,0]
print(dailyTemperatures([30,60,90])) # 输出: [1,1,0]
代码解析
-
初始化答案数组和栈：
answer初始化为长度为n的数组，所有元素为0。stack用于存储温度的索引，保持单调递减的顺序。
-
遍历温度数组：
- 使用
enumerate遍历温度数组，同时获取索引和温度值。
- 使用
-
更新答案并弹出栈顶元素：
- 如果当前温度大于栈顶温度，说明找到了一个更高的温度，计算天数差并更新答案数组，然后弹出栈顶元素。
- 重复上述步骤，直到栈为空或当前温度小于等于栈顶温度。
-
当前索引入栈：
- 将当前索引入栈，继续遍历。
-
返回答案数组：
- 最终返回答案数组
answer。
- 最终返回答案数组
复杂度分析
- 时间复杂度：O(n)，其中
n是数组的长度。每个元素最多入栈和出栈一次。 - 空间复杂度：O(n)，栈的大小最多为
n。
示例运行
示例 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]
总结
通过使用单调栈，我们可以高效地找到每个温度之后的第一个更高温度。这种方法不仅简洁，而且效率非常高，适合处理类似的问题。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！
关注我，获取更多算法题解和编程技巧！
