739. Daily Temperatures
给你每天的气温，要你对每天算出到下一次气温比他高要隔几天
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]
以第三天的75为例，下次比他高是76 -> 中间隔了四天
Example 2:
Input: temperatures = [30,40,50,60]
Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]
Output: [1,1,0]
思路:
1.这种找下个比他大的题型可以用 monotonic stack
维护一个递减的 stack，看新加入的人有没有机会更新前面的人
如果 stack[-1] 比新加入的小 代表 stack[-1] 后遇到第一个比他大的人就是新加入的
这时候就 pop 并且结算 stack[-1] (因为他找到第一个比他大的了)
直到 stack[-1] 比大于等于新加入的 这时候就能 append 他
整个 stack 依然会维持递减
2.隔几天就是要看 index 差多少，所以 stack 要存 index
Python code:
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stk = []
res = [0]*len(temperatures)
for i, t in enumerate(temperatures):
while stk and temperatures[stk[-1]] < t:
res[stk[-1]] = i-stk[-1]
del stk[-1]
stk.append(i)
return res
最近好冷