The Monotonic Stack: Next Greater Element

The problem

For each day's temperature, find the next day that is warmer. Checking forward from every day is O(n²). A stack can do it in one pass.

The idea

Keep a stack of days that are still waiting for a warmer day. Their temperatures on the stack only ever go down from bottom to top (that's why it's called monotonic). When a warmer day arrives, it answers every waiting day that's cooler – pop them off.

Think of it like this: People in a queue waiting for someone taller to arrive. When a tall person walks in, everyone shorter who was waiting gets their answer and leaves.

def next_warmer(temps):
    answer = [-1] * len(temps)
    waiting = []                         # indexes of days still waiting
    for i, t in enumerate(temps):
        while waiting and temps[waiting[-1]] < t:
            day = waiting.pop()
            answer[day] = t              # today is that day's next warmer temperature
        waiting.append(i)
    return answer

temps = [30, 28, 32, 31, 29, 35]
print(next_warmer(temps))

Output

[32, 32, 35, 35, 35, -1]

Each day is pushed once and popped at most once, so the total work is O(n).

Remember: Whenever a problem says “the next bigger” or “the previous smaller” item, think monotonic stack.