The Monotonic Stack

The idea

Push elements onto a stack, but before each push remove everything the newcomer makes irrelevant. What remains is sorted, and each removal tells you something.

python

1def next_greater(nums):2    result = [-1] * len(nums)3    stack = []                      # indices, values strictly decreasing4 5    for index, value in enumerate(nums):6        while stack and nums[stack[-1]] < value:7            result[stack.pop()] = value   # THIS is the discovery8        stack.append(index)9 10    return result

Next greater element

Concept

Popping is the answer, not cleanup

It is tempting to read the while loop as tidying up before the push. It is not: the moment an element is popped, you have just learned its next greater element. Write the answer there.

Concept

Why the nested loop is linear

Each index is pushed exactly once and popped at most once. The inner while loop can run many times in one iteration, but across the whole scan it cannot run more than n times in total. That is an amortised argument, and it is why O(n) is correct despite the nesting.

The deque variant

A sliding-window maximum needs the same idea plus expiry from the front, because an element can leave the window without ever being beaten. That makes it a deque rather than a stack.

Only useful candidates survive

Inputrates = [1, 3, -1, -3, 5], k = 3

deque [1]push
deque [3]3 beats 1, so 1 can never matter again
deque [3, -1]-1 might matter once 3 expires
deque [5]5 beats everything present

Result[3, 3, 5]

Can you recognise the pattern?

Each element needs to know about the nearest larger or smaller element in some direction.

Quick quiz

The idea

Popping is the answer, not cleanup

Why the nested loop is linear

The deque variant