The Monotonic Stack

This animation runs the next-greater scan on a row of histogram bars, with the stack drawn as a tower on the right.

As the scanner crosses each bar, watch two things happen. First, any stack entry smaller than the current bar pops off and arcs over to its answer slot — the current bar is the first greater value that entry ever met, so the current bar is its "next greater". Second, the current bar slides onto the stack.

The key invariant to watch: the tower never stops being sorted. Bigger bars sit at the bottom, smaller near the top, at every single frame. That is not a coincidence — the pops before each push are exactly what enforces it. A bar only sits on the stack while it is still waiting for something greater to arrive.

Also notice the cost. Some steps pop three entries, some pop none, but every bar is pushed exactly once and popped at most once. Count total pushes and pops at the end: about 2n moves for n bars. That is why this "loop inside a loop" is O(n), not O(n squared).

Bars still in the tower when the scan ends never met a greater value — their answer stays "none".