题目描述:
请根据每日 气温 列表,重新生成一个列表。对应位置的输出为:要想观测到更高的气温,至少需要等待的天数。如果气温在这之后都不会升高,请在该位置用 0 来代替。
例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
思路:
要求从前往后找第一次出现比当前值大的
求解时,从后往前遍历,设置一个栈,如果栈为空,直接放入,最终结果中存放0,如果栈不空,当前值比栈顶小,求当前值和栈顶的索引之差,然后将索引放入栈顶,如果当前值比栈顶大,循环输出栈顶元素(因为要找出现第一次比当前值大的地方),这时还要判断栈是否空,如果栈空,将当前值直接放入,否则求当前值和栈顶的索引之差,再把当前值放入栈中
1 class Solution:
2 def dailyTemperatures(self, T: List[int]) -> List[int]:
3 stack = []
4 res = []
5 for i in range(len(T)-1,-1,-1):
6 if not stack:
7 stack.append(i)
8 res.append(0)
9 else:
10
11 while stack and T[i]>=T[stack[-1]] : # 先判断栈是否空,再取栈中的值,否则下标越界
12 stack.pop()
13 if not stack:
14 res.append(0)
15 else:
16 res.append(stack[-1]-i)
17 stack.append(i)
18 res.reverse() # 返回none
19 #return [res[i] for i in range(len(res)-1,-1,-1)]
20 return res
原文:https://www.cnblogs.com/shuangcao/p/13656981.html