How do you solve the daily temperatures problem with a monotonic stack?
You use a stack of the days that are still waiting for a warmer day, and you keep the temperatures on the stack in decreasing order.
def daily_temperatures(temps):
result = [0] * len(temps)
stack = []
for i, temp in enumerate(temps):
while stack and temps[stack[-1]] < temp:
waiting = stack.pop()
result[waiting] = i - waiting
stack.append(i)
return result
So what is the question asking? For each day it asks how many days you have to wait before a day that is warmer than that one. So the answer for a day is the number of days between it and the next warmer day, and it is zero when no warmer day ever comes.
And how does the stack version work? The stack holds the days that have not found their warmer day yet, and the temperatures on it are in decreasing order. When a new day arrives with a temperature that is warmer than the one on top of the stack, then this day is the answer for that waiting day, and the number of days you waited is the difference between the two positions.
the temps the stack what happens
----------- ---------- ---------------------------
[73, 74] [] push the day 0
[73, 74] [0] 74 is warmer, the answer for day 0 is 1
the answer [1, 0]
And the line that pops is stack.pop() and the answer is i - waiting. The difference between the two positions is the number of days you had to wait. If the warmer day is the next day then the difference is one, and if it is three days later then the difference is three.
And the days that are still on the stack at the end never found a warmer day, so their answers stay at zero. That is why the result list starts as all zeros and you only write over the ones you find.
And the complexity is O of n for the time, because every day goes on the stack once and comes off once, and O of n for the space.
So the rule to remember is this. The answer is the difference between the two positions, and the days that never get an answer stay at zero.
The last question in this topic shows the slow version.