Given a list of daily temperatures
T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put
0instead. For example, given the list of temperatures
T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be
[1, 1, 4, 2, 1, 1, 0, 0]. Note: The length of
temperatureswill be in the range
[1, 30000]. Each temperature will be an integer in the range
This is a great exercise for Monotonic Stack. Monotonic stack is a stack when the items in it are kept in order (monotonically increasing or monotonically decreasing). One of the properties of it is that:
- With a monotonically increasing stack, you can find the first item that is smaller than each item.
- With a monotonically decreasing stack, you can find the first item that is larger than each item.
We use monotonically decreasing stack
mono. Iterating from the left to the right:
- when we meet an element that is smaller than the top element in
mono, we would push it to
- when we meet an element that is larger than the top element in
mono, we pop it.
class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: mono,n = ,len(T) ret =  * n for i,val in enumerate(T): while mono and val > mono[-1]: pre_i,pre_v = mono.pop() ret[pre_i] = i - pre_i mono.append((i,val)) return ret