Monotonic stack and deque
Keep the elements whose question is still open on a stack. Because a bigger one would already have answered them, what is waiting is always sorted, and one arrival can settle several at once.
Problems worked on this page, and more to practise
- 739. Daily Temperatures
- 239. Sliding Window Maximum
- 84. Largest Rectangle in Histogram
- 496. Next Greater Element I
- 503. Next Greater Element II
- 901. Online Stock Span
- 907. Sum of Subarray Minimums
- 402. Remove K Digits
- 316. Remove Duplicate Letters
- 456. 132 Pattern
- 42. Trapping Rain Water
- 85. Maximal Rectangle
- 862. Shortest Subarray with Sum at Least K
What is a monotonic stack?
A plain stack that you keep sorted by never letting an out-of-order element sit on it: before pushing, you pop everything the newcomer would break the order against. In this pattern the stack holds the indices whose question is not answered yet, and the order comes for free, because an index only stays unanswered while nothing bigger has arrived after it. Store indices rather than values, so you can still compute distances and widths.
When should I use a monotonic stack?
When the question is, for every element, the nearest element in one direction that is bigger or smaller. Daily Temperatures, Next Greater Element, Largest Rectangle in Histogram and Trapping Rain Water are all that question in disguise. If the question asks for the maximum of every fixed-size window instead, the same idea with a deque answers it, because an index then has two reasons to leave.
Why is a monotonic stack O(n) when it has a loop inside a loop?
Count the pops across the whole scan rather than per step. Each index is pushed exactly once and can be popped at most once, so the inner while loop runs at most n times in total, not n times per outer step. One step can pop five indices, but then five later steps pop nothing. The scan is n pushes plus at most n pops.
Should the comparison be strict or not?
It decides what happens to equal values, and it is the usual source of a wrong answer on duplicates. For Daily Temperatures the answer must be strictly warmer, so an equal temperature does not settle the wait and the test is strict. For the sliding-window deque the non-strict test is right, because an older index with the same value leaves the window sooner and can never be needed. Work out on paper what two equal values should do, then pick the operator that does it.
What is the difference between a monotonic stack and a monotonic deque?
The stack has one rule: drop from the top whatever the newcomer dominates. The deque adds a second rule: drop from the front whatever has fallen out of the window. Both removals are cheap, they happen at opposite ends, and that second rule is the only reason a deque is needed at all.