LeetCode 739. 每日温度 | Python

739. 每日温度

题目来源：力扣（LeetCode）leetcode-cn.com/problems/da…

题目

根据每日 气温 列表，请重新生成一个列表，对应位置的输出是需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。

例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。

解题思路

思路：单调栈

先理清题意，题目中的意思是每个元素往右边找到第一个比它大的元素，计算两者间的距离。

那么使用暴力解的话，代码大致如下：

python copyable">defdailyTemperatures(self, T: List[int]) -> List[int]:
length = len(T)
ans = [0] * length
for i in range(length):
for j in range(i+1, length):
if T[i] < T[j]:
ans[i] = j - i
break
return ans

这里，执行会超时。

我们需要去优化，使用栈，用空间换时间。

从前面的暴力解也可以看出来，解决问题主要需要关注的就是右边的元素的大小。

先看看暴力解的主要问题，在遍历数组的时候，寻找下一个元素比当前元素大这块，很大程度都在做重复的查询。

现在希望能够解决的就是，使用栈存储右边的元素，供后续比较，将无需重复比较的元素剔除。

现在我们考虑从右边进行遍历，考虑哪些元素需要剔除？

当我们从右边往左开始遍历时，要保留较大的元素入栈，具体的做法：

  • 当栈为空的情况下，将当前元素入栈；

  • 遍历的时候，如果当前元素比栈顶元素大时，这个时候考虑将栈内的元素出栈，直到栈顶元素大于当前元素；

  • 这个时候，栈顶的元素其实就是当前元素右边第一个比其大的元素，先计算距离，然后将当前的元素入栈，继续遍历

  • 重复上面的步骤，直至遍历结束。

具体的代码实现如下。

代码实现

classSolution:
defdailyTemperatures(self, T: List[int]) -> List[int]:
length = len(T)
ans = [0] * length
# 这里借助列表实现
# 列表末尾元素即是栈顶元素
stack = []
# 从右边往左边开始遍历
for i in range(length - 1, -1, -1):
# 如果当前元素大于等于栈顶元素时，进行出栈
# 直至当前元素小于栈顶元素
while stack and T[i] >= T[stack[-1]]:
stack.pop()
# 这个时候栈顶元素其实就是当前元素右边第一个比其大的元素，先计算距离，然后入栈
if stack and T[i] < T[stack[-1]]:
ans[i] = stack[-1] - i
# 栈为空的情况下，将当前元素入栈
stack.append(i)
return ans

实现结果

实现结果

总结

  • 先理清题意，题目要求的是每个元素往右找第一个比它大的元素，计算两者间的距离。

  • 先使用暴力解尝试解决问题（Python 编写超时），但是可以发现有部分查询是重复的。尝试使用空间换时间的思路优化。

  • 借助栈，从右往左开始遍历。维护栈内的元素，避免重复查询。具体的做法（遍历从右往左）：

    • 当栈为空时，元素入栈；

    • 遍历时，当前元素大于等于栈顶元素时，这个时候要进行出栈，直至当前元素小于栈顶元素；

    • 这个时候栈顶元素其实就是当前元素右边第一个比它大的元素，计算两者间的距离，然后将当前元素入栈。供下一个 i-1 索引元素作比较。（在这里，前面出栈的元素为何可以剔除，是因为比当前 T[i] 还小的元素，不可能是 T[i-1] 右边第一个比它大的元素）

    • 继续遍历直至结束。

文章原创，如果觉得写得还可以，欢迎关注。微信公众号《书所集录》同步更新，同样欢迎关注。

以上是 LeetCode 739. 每日温度 | Python 的全部内容， 来源链接： utcz.com/a/23428.html

回到顶部