Monotonic Stack

A monotonic stack finds the next bigger (or smaller) value for every element in one pass. Each new element pops everything it beats, so the stack stays sorted, and since every element is pushed once and popped at most once the scan is $O(n)$.

Variant	Kept in order	Typical use
Decreasing stack	Largest at the bottom	Next or previous greater
Increasing stack	Smallest at the bottom	Next smaller, spans, areas
Monotonic deque	Sorted, expires from the front	Max or min of each window

The comparison is where people slip. Popping on < versus <= decides how equal values behave. When you count the subarrays each element is the minimum of, spans that stop only at strictly smaller values on both sides count a tie twice, and spans that stop at smaller-or-equal values on both sides miss it, so make one side strict and the other not. A monotonic deque also drops indexes from the front once they slide out of the window.

Approach	Time	Extra space
Scan forward from every element	$O(n^2)$	$O(1)$
Heap or sorted set	$O(n \log n)$	$O(n)$
Monotonic stack or deque	$O(n)$	$O(n)$

Use it when a problem asks for the nearest bigger or smaller element, how far each value stays the minimum, or the extreme of every sliding window.

The problems below start with next greater and next smaller, move through a circular array, subarray minimums and the largest rectangle, then switch to deques for sliding windows and prefix sums.