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] 范围内的整数。
解题思路
思路：单调栈
先理清题意，题目中的意思是每个元素往右边找到第一个比它大的元素，计算两者间的距离。
那么使用暴力解的话，代码大致如下：
def dailyTemperatures(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
这里，执行会超时。
我们需要去优化，使用栈，用空间换时间。
从前面的暴力解也可以看出来，解决问题主要需要关注的就是右边的元素的大小。
先看看暴力解的主要问题，在遍历数组的时候，寻找下一个元素比当前元素大这块，很大程度都在做重复的查询。
现在希望能够解决的就是，使用栈存储右边的元素，供后续比较，将无需重复比较的元素剔除。
现在我们考虑从右边进行遍历，考虑哪些元素需要剔除？
当我们从右边往左开始遍历时，要保留较大的元素入栈，具体的做法：
- 当栈为空的情况下，将当前元素入栈；
- 遍历的时候，如果当前元素比栈顶元素大时，这个时候考虑将栈内的元素出栈，直到栈顶元素大于当前元素；
- 这个时候，栈顶的元素其实就是当前元素右边第一个比其大的元素，先计算距离，然后将当前的元素入栈，继续遍历
- 重复上面的步骤，直至遍历结束。
具体的代码实现如下。
代码实现
class Solution:
def dailyTemperatures(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] 右边第一个比它大的元素） - 继续遍历直至结束。
文章原创，如果觉得写得还可以，欢迎关注。微信公众号《书所集录》同步更新，同样欢迎关注。
网友评论