Monotonic Stack
A monotonic stack is a stack whose elements stay in either increasing or decreasing order as you push. It solves problems like finding the next greater element, daily temperatures, and largest rectangle in a histogram in a single linear pass.
How it works
Walk through the array once. Before pushing a new element, pop everything on the stack that violates the ordering you want to keep:
- For a decreasing stack, pop while the top is smaller than the new element.
- Each popped element has just found its answer, because the new element is the first one that broke its run.
Because every element is pushed and popped at most once, the total work is linear even though there is a loop inside the loop.
Why it is clever
The stack lets you defer decisions. An element waits until a later value resolves it, so you never rescan earlier positions.
Key idea
Keep the stack sorted so each pop instantly resolves an element with the value that broke its order.