共计 933 个字符,预计需要花费 3 分钟才能阅读完成。
题目
给定一个整数数组 temperatures,示意每天的温度,返回一个数组 answer,其中 answer[i] 是指在第 i 天之后,才会有更高的温度。如果气温在这之后都不会升高,请在该地位用 0 来代替。
输出: temperatures = [73,74,75,71,69,72,76,73]
输入: [1,1,4,2,1,1,0,0]
输出: temperatures = [30,40,50,60]
输入: [1,1,1,0]
输出: temperatures = [30,60,90]
输入: [1,1,0]
其实就是,找出数组中每一个元素的左边第一个比他大的元素间隔本人的下标差。
思路:枯燥栈
遍历数组,每个元素进入栈,
入栈前,该元素和栈顶元素比拟大小,大于栈顶元素,则栈顶元素找到了第一个比他大的元素,计算下标差,弹出栈顶元素
该元素再和新的栈顶元素比拟大小,反复上述过程
直到该元素小于栈顶元素,或空栈,将该元素入栈
例如:
开始遍历
73,入栈【73】
74,大于 73,计算 74 与 73 在原数组中的下标差,弹出 73【】,74 入栈【74】
75,大于 74,计算 75 与 74 在原数组中的下标差,弹出 74【】,75 入栈【75】
71,小于 75,入栈【75,71】
69,小于 71,入栈【75,71,69】
72,大于 69,计算 72 和 69 在原数组中的下标差,弹出 69【75,71】
- 大于 71,计算 72 和 71 在原数组中的下标差,弹出 71【75】
- 小于 75,72 入栈【75,72】
76,大于 72,计算 76 和 72 在原数组中的下标差,弹出 72【75】
- 大于 75,计算 76 和 75 在原数组中的下标差,弹出 75【】,76 入栈【76】
73,小于 76,入栈【76,73】
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = []
n = len(temperatures)
res = [0]*n
for i in range(n):
while stack and temperatures[i] > temperatures[stack[-1]] :
preIndex = stack.pop()
res[preIndex]=i-preIndex
stack.append(i)
return res
正文完