A monotonic stack maintains its elements in strictly increasing (or decreasing) order. Before pushing a new value, pop everything that violates the order. The popped elements often have useful structural meaning — they were "ended" by the new value.
Next greater element
For each element in an array, find the next element to its right that's larger. Scan left to right with a decreasing stack of indices. When you hit a value larger than stack's top, pop and assign the current value as the popped element's "next greater." Push the current index. total — each index is pushed and popped at most once.
Largest rectangle in a histogram
For each bar, find the largest rectangle that uses it as the minimum height. The rectangle's width is the span between the nearest shorter bar on the left and the nearest shorter bar on the right. Use a monotonic increasing stack to find both spans in .
Daily temperatures
Given daily temperatures, return how many days until a warmer day for each entry. Same pattern as next-greater-element, with the answer being the index distance rather than the value.
Why $O(n)$
The amortized argument: each element is pushed exactly once and popped at most once. Even though the inner while-loop can pop multiple elements, the total work across all iterations is bounded by .
Recognition
Monotonic stack problems usually phrase the question as "for each element, find the next/previous larger/smaller element." That's the trigger — almost always solvable in linear time with this pattern.