Daily Temperatures

Intuition

A day only needs to remember the earlier days that have not yet found a warmer temperature. Keep those days' indices on a stack whose temperatures are non-increasing. When the current day is warmer than the day at the top of the stack, that top day has found its warmer day, and the wait is simply the difference in indices. Keep popping while the current day beats the top, resolving each one, then push the current index to wait for its own warmer day. Every index is pushed and popped once, so the whole process is linear.

Algorithm walkthrough

1. 1Create an answer array filled with 0 and an empty stack of indices.
2. 2Iterate i over the days. While the stack is non-empty and temperatures[i] is greater than temperatures at the top index, pop that index j.
3. 3Set answer[j] = i - j, the number of days day j waited.
4. 4Push i onto the stack so it can wait for a warmer future day.
5. 5Any indices remaining on the stack keep their default answer of 0 because no warmer day ever appeared.

Implementation

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        n = len(temperatures)
        answer = [0] * n
        stack = []
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                j = stack.pop()
                answer[j] = i - j
            stack.append(i)
        return answer