動機
現在只要用到stack就會讓我想到merge interval
Problem
Given an array of integers temperatures
represents the daily temperatures, return an array answer
such that answer[i]
is the number of days you have to wait after the ith
day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0
instead.
Example 1:
Input: temperatures = [73,74,75,71,69,72,76,73]Output: [1,1,4,2,1,1,0,0]
Example 2:
Input: temperatures = [30,40,50,60]Output: [1,1,1,0]
Example 3:
Input: temperatures = [30,60,90]Output: [1,1,0]
Constraints:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
Sol
stack的promise是底下的大於上面的
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
stk = [len(T)-1] # promise: stk[i] > stk[j]
ret = [0]
for i in reversed(range(len(T)-1)):
while stk and T[stk[-1]] <= T[i]:
stk.pop()
if not stk:
ret.append(0)
else:
ret.append(stk[-1]-i)
stk.append(i)
ret.reverse()
return ret