What is a monotonic stack? Show how to solve "next greater element".
Monotonic stack turns a class of O(n²) problems into O(n) — interviewers use it to separate pattern-recognizers from brute-forcers.
Definition: a stack whose elements are monotonically increasing or decreasing. We maintain monotonicity by popping violators before pushing.
Next greater element: iterate nums; while stack.top <= nums[i], pop and record nums[i] as their answer. Push nums[i]. At end, remaining stack elements have no greater.
Largest rectangle in histogram: for each bar, find left and right boundaries where height drops below it. Monotonic increasing stack gets this in one pass.
Pattern: "for each element, find the nearest element on left/right that is larger/smaller" → monotonic stack.
Amortized O(n) because every element pushed and popped at most once.
A monotonic stack keeps its elements in increasing or decreasing order by popping any violator before pushing. For 'next greater element': iterate the array, and while the stack top is <= current, pop it — the current element is its answer. Push current. Any element left on the stack at the end has no greater to its right. The whole thing is O(n) because every index is pushed and popped exactly once — classic amortized analysis. Pattern match: whenever the problem is 'for each i, find the nearest j to the left/right with property P', try monotonic stack. 'Daily temperatures', 'largest rectangle in histogram', 'trapping rain water', 'remove k digits' — all the same shape.
Store indices in the stack, not values, when you need positions or distances.
For "previous smaller" swap the direction; for "next smaller" flip the comparator.
HireMe AI (即答侠) has the template plus 6 problem variants — once you see the shape once, the rest are 1:1.
Related but different. Monotonic queue (deque) also supports removing from the other end — used for sliding-window max.
When the question doesn't ask about "nearest with property" — e.g. "k-th larger" needs a heap, not a monotonic stack.
HireMe AI listens to your interview in real-time, detects questions, and generates instant answer suggestions — so you never freeze up again.
Try HireMe AI Free