Python实现 LeetCode 739. 每日温度

739. 每日温度
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/daily-temperatures

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

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

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

解题思路
思路:单调栈

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

那么使用暴力解的话,代码大致如下:

这里,执行会超时。

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

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

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

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

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

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

当栈为空的情况下,将当前元素入栈;
遍历的时候,如果当前元素比栈顶元素大时,这个时候考虑将栈内的元素出栈,直到栈顶元素大于当前元素;
这个时候,栈顶的元素其实就是当前元素右边第一个比其大的元素,先计算距离,然后将当前的元素入栈,继续遍历
重复上面的步骤,直至遍历结束。
具体的代码实现如下。

代码实现

实现结果

总结
先理清题意,题目要求的是每个元素往右找第一个比它大的元素,计算两者间的距离。
先使用暴力解尝试解决问题(Python 编写超时),但是可以发现有部分查询是重复的。尝试使用空间换时间的思路优化。
借助栈,从右往左开始遍历。维护栈内的元素,避免重复查询。具体的做法(遍历从右往左):
当栈为空时,元素入栈;
遍历时,当前元素大于等于栈顶元素时,这个时候要进行出栈,直至当前元素小于栈顶元素;
这个时候栈顶元素其实就是当前元素右边第一个比它大的元素,计算两者间的距离,然后将当前元素入栈。供下一个 i-1 索引元素作比较。(在这里,前面出栈的元素为何可以剔除,是因为比当前 T[i] 还小的元素,不可能是 T[i-1] 右边第一个比它大的元素)
继续遍历直至结束。

发表评论

文章信息
字数 799
价格 免费
购买人数 0
作者信息
吾生也有涯,而知也无涯。——庄子