Card 01/ 08
Monotonic Stack: The Next Greater Value for Every Position
Keep the positions still waiting for a larger value on a stack, and each new value answers every smaller one waiting on top.
A monotonic stack finds, for every position of an array, the nearest later value that is larger, in one pass. The cue is a property of the problem: each position needs the nearest value after it, or before it, that is larger, or smaller. A stack is a collection where the last item pushed on is the first popped off, and the Stacks and Queues topic in Data Structures builds one. A monotonic stack is a stack whose items stay in sorted order.
Here the stack holds the positions not yet answered, and its invariant is that their values decrease from bottom to top. When a new value arrives, every waiting position on top with a smaller value has found its answer: pop it and record the new value. Then push the new position, which keeps the order. Positions still on the stack at the end have no larger value after them, and their answer is −1.
The values 4 1 6 2 3 5 show it.
What is the next greater value for each position?
6 6 −1 3 5 −1. The steps show each position waiting on the stack until a larger value answers it; a blank in the answer row is a position still waiting.
One pass over 4 1 6 2 3 5 with a stack of waiting positions
Position 0, value 4
4 1 6 2 3 5
^
stack (indices): 0
answer: _ _ _ _ _ _Position 1, value 1
4 1 6 2 3 5
^
stack (indices): 0 1
answer: _ _ _ _ _ _Position 2, value 6: answers positions 1 and 0
4 1 6 2 3 5
^
stack (indices): 2
answer: 6 6 _ _ _ _Position 3, value 2
4 1 6 2 3 5
^
stack (indices): 2 3
answer: 6 6 _ _ _ _Position 4, value 3: answers position 3
4 1 6 2 3 5
^
stack (indices): 2 4
answer: 6 6 _ 3 _ _Position 5, value 5: answers position 4
4 1 6 2 3 5
^
stack (indices): 2 5
answer: 6 6 _ 3 5 _Positions 2 and 5 are left on the stack, so their answer is −1. The 6 at position 2 answered two positions in one step, and the 5 at position 5 passed over the 6 without popping it, because the stack only pops while the top is smaller.
A crowd of people each waiting to see someone taller arrive works the same way: a tall arrival answers everyone shorter at the back of the waiting group, and they leave. The likeness breaks at the exit. A real crowd could let anyone leave in any order, while the stack lets go only from the top, which is safe only because the waiting values decrease towards the top, so everyone the arrival beats is on top.
Like a sliding window, the stack keeps only the candidates still alive and drops each one for good once it is answered, which is why the pass is O(n).
← → move through sections and cards