THE MONOTONIC STACK — a dart

THE MONOTONIC STACK next-greater-element in one pass — the undecided wait on a stack

For each element, what is the next greater element to its right? The monotonic stack answers all of them in a single pass. It holds the indices of values still waiting for their answer, kept in decreasing order. Each new value resolves everything on top of the stack it exceeds (they have found their next-greater — it is the newcomer), popping them, then joins the stack to wait its own turn. Every element is pushed once and popped once: O(n) for what looks like an O(n²) question. The stack is the bounded memory of “questions not yet answered,” and it drains as answers arrive.

THE TECHNIQUE decreasing stack of the undecided; a bigger value resolves them

A short array. The demo finds the next-greater-element of the first value, using the monotonic stack: live demo

HISTORY & CREDIT next-greater-element · stack folklore

“Next-greater-element is a quadratic scan.” — a stack of the undecided makes it linear: each value waits once and is resolved once, the instant a larger value appears. cited

folklore · the monotonic-stack pattern for next-greater / next-smaller / span problems.
relatives · the stock-span problem, the largest rectangle in a histogram (nolinear without it), the maximal-rectangle DP.
now · a staple one-pass technique in compilers (bracket/precedence), parsing, and array processing.

A stack of open questions; each newcomer closes the ones it towers over. Linear answers to a quadratic-looking ask. monotonic stack

RECOMMEND FOR I-13 the next-greater-element, on the compiler

On the canonical compiler, the next-greater-element of 2 in [2,1,5,3] is 5 — found in one forward pass:

$ i13 run op_monostack.i13 # first value to the right that exceeds a[0] RUN OK · 48 step(s) · peak stack 5 · call depth 2 nge_first = 5 -- resolved in one pass, no quadratic rescan

Recommend: the monotonic stack is the one-pass sibling of the monotonic queue — the same “evict the dominated” idea, applied to waiting questions instead of window candidates. i13 finds the next-greater of 2 to be 5. The supplement to correctness: a correct nested scan re-reads the tail for every element; the stack resolves each exactly once. Like the queue it is an efficiency mechanism, not a structural keeper, and (honestly) i13 computes the single answer here rather than driving the full stack — but it completes the batch's pair of “push-once, pop-once” forgetting structures.