Monotonic stack: daily temperatures

You've got a week's worth of daily temperatures and one nagging question for each day: how many days until it gets warmer? For every day i, return the number of days you have to wait for a strictly warmer temperature. If no warmer day ever comes, the answer is 0.

The brute-force urge is to scan forward from each day — that's O(n²). The slick trick is a monotonic stack: a stack that only ever holds indices of days still waiting for a warmer day, kept in decreasing temperature order.

Walk left to right. When today's temperature is warmer than the day sitting on top of the stack, that older day's wait is over — pop it and record the gap (today's index minus its index). Keep popping while today beats the top, then push today on to wait its turn.

stack = []                       # indices of days still waiting
for i, t in enumerate(temps):
    while stack and temps[stack[-1]] < t:
        j = stack.pop()
        answer[j] = i - j        # j finally found a warmer day
    stack.append(i)

Each index is pushed once and popped at most once, so the whole thing is O(n). Anything left on the stack at the end never warmed up, so it keeps its 0.

Your task

Write daily_temperatures(temps) that returns a list where result[i] is the number of days until a warmer temperature, or 0 if there is none.

daily_temperatures([73,74,75,71,69,72,76,73])  # [1, 1, 4, 2, 1, 1, 0, 0]
daily_temperatures([30,40,50,60])              # [1, 1, 1, 0]
daily_temperatures([30,60,90])                 # [1, 1, 0]
daily_temperatures([50])                       # [0]

Hint: initialise the answer to all zeros, then a monotonic stack only ever fills in the days that actually find a warmer future.