Monotonic Stack / Queue
A monotonic stack maintains elements in strictly increasing or decreasing order. Elements that violate the order are popped before the new element is pushed, enabling O(n) solutions for 'next greater element' problems.
Monotonic stack = a line of increasingly tall people. When a taller person arrives, shorter people in front get eliminated because they'll never be 'seen' again. Each person enters and exits the line exactly once.
Next greater element: iterate left to right, maintain a decreasing stack. When new element arr[i] > stack top, the top's 'next greater' is arr[i] — pop and record. Push arr[i]. O(n) time — each element pushed and popped once. Monotonic deque (sliding window maximum): use a deque that is decreasing front-to-back; remove elements from front when they're out of window, remove from back when new element is larger. O(n) for all n windows.
Monotonic stack problems: largest rectangle in histogram (maintain increasing stack of heights, pop when smaller height seen — compute area using popped height and current width), trapping rain water (two-pointer or monotonic stack approach), daily temperatures. The pattern is: whenever you pop an element, you've found the 'previous greater' or 'next smaller' relationship for that element — record the answer at pop time. For all-at-once processing, this yields O(n) solutions to problems that naively require O(n²) comparisons. Stock span problem generalizes this: span of day i = days since the last day with a higher price.
Monotonic stack is my first thought when I see 'next greater/smaller element', 'largest rectangle', or 'trapping rain water'. The invariant is simple: when I pop an element, I've found the element that broke the monotonic property — and that relationship (next greater, previous smaller, etc.) is what I record as the answer for the popped element. Each element is pushed and popped at most once → O(n). I apply the same idea with a deque for sliding window maximum, where I additionally remove expired elements from the front.
Monotonic stack problems require careful handling of elements with equal values. For 'next greater' (strictly greater), elements equal to the stack top should NOT trigger a pop — they should be pushed on top. For 'next greater or equal', equal values should pop. Getting this wrong causes incorrect answers on inputs with duplicates.