华为 OD 训练营 · 题解精讲
LC739. 每日温度
LC739. 每日温度 视频讲解。
题目描述
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。 例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。 提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
题目解析
这道题目最 “难” 的一个点是题目的理解。 给定列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，为啥输出就是 [1, 1, 4, 2, 1, 1, 0, 0] ？ 下面来一个个进行解释。 对于输入 73，它需要 经过一天 才能等到温度的升高，也就是在第二天的时候，温度升高到 74 ，所以对应的结果是 1。 对于输入 74，它需要 经过一天 才能等到温度的升高，也就是在第三天的时候，温度升高到 75 ，所以对应的结果是 1。 对于输入 75，它经过 1 天后发现温度是 71，没有超过它，继续等，一直 等了四天，在第七天才等到温度的升高，温度升高到 76 ，所以对应的结果是 4 。 对于输入 71，它经过 1 天后发现温度是 69，没有超过它，继续等，一直 等了两天，在第六天才等到温度的升高，温度升高到 72 ，所以对应的结果是 2 。 对于输入 69，它 经过一天 后发现温度是 72，已经超过它，所以对应的结果是 1 。 对于输入 72，它 经过一天 后发现温度是 76，已经超过它，所以对应的结果是 1 。 对于输入 76，后续 没有温度 可以超过它，所以对应的结果是 0 。 对于输入 73，后续 没有温度 可以超过它，所以对应的结果是 0 。 也就是说，这道题目就是给你一个值，让你找到右边第一个比它大的数，它们两则的下标差就是输出结果。 好了，理解了题意我们来思考如何求解：借助单调递增栈来处理。 具体操作如下： 遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递增栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。 继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，再将数字入栈，这样就可以一直保持递增栈，且每个数字和第一个大于它的数的距离也可以算出来。
参考代码
参考代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 每日温度（ LeetCode 739 ）：https://leetcode-cn.com/problems/daily-temperatures
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
# 构建一个栈,用来存放每日温度的下标
stack = []
# 获取数组长度
length = len(temperatures)
# 构建一个数组，用来保存输出结果
res = [0] * length
# 从头开始遍历每天的温度
for i in range(length):
# 拿到当天的温度，不断的和栈顶元素进行比较
temperature = temperatures[i]
# 如果栈顶元素存在并且当天的温度大于栈顶元素
# 意味着栈顶元素等到了第一个温度比它更高的那一天
# 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果
while stack and temperature > temperatures[stack[-1]]:
# 首先获取栈顶元素的值，也就是每日温度的下标值
preIndex = stack.pop()
# 它们的下标差就是栈顶元素等了多少天等到的更高温度的结果，保存到输出数组 res 中
res[preIndex] = i - preIndex
# 再把当天的温度的下标值存放到栈中
# 注意：是下标索引值
stack.append(i)
# 最后输出 res 数组即可
return res
四、复杂度分析
时间复杂度：O(n)，其中 n 是温度列表的长度。正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
空间复杂度：O(n)，其中 n 是温度列表的长度。需要维护一个单调栈存储温度列表中的下标。