Monotonic Stack

A monotonic stack keeps values or indexes in increasing or decreasing order as the algorithm scans a sequence.

It is useful for nearest-greater, nearest-smaller, and span-like problems.

Core Idea

When a new value arrives, the stack removes values that can no longer be useful. The remaining stack preserves a useful order.

Each element is pushed once and popped at most once, so many monotonic stack algorithms are linear.

Python Example

def next_greater(values):
    answer = [-1] * len(values)
    stack = []
 
    for i, value in enumerate(values):
        while stack and values[stack[-1]] < value:
            index = stack.pop()
            answer[index] = value
        stack.append(i)
 
    return answer

The stack stores indexes whose next greater value has not been found yet.

Common Confusions

The stack usually stores indexes, not just values, because the algorithm often needs to write answers back to the original positions.

“Monotonic” describes the stack’s maintained order. It does not mean the input sequence itself is sorted.

When To Use It

Use a monotonic stack for next greater element, previous smaller element, histogram rectangles, stock span, and problems where a nearer stronger value makes weaker candidates obsolete.