Monotonic Stack
A new value pops everything it beats before it lands, so the stack stays sorted. For next-greater, each pop hands the popped value its answer. For previous-greater, each pop throws away a value that can never be an answer again, and whatever is left on top is the answer.
For each value, find the first greater value to its right. Scan left to right. The stack holds values still waiting for their answer, bottom to top.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 9, with their answers.
Top of the stack is 4, the new value is 3. Pop or push?
Answer: Push 3. 4 is not beaten, so it cannot be resolved yet. 3 joins the wait above it.
Top of the stack is 3, the new value is 1. Pop or push?
Answer: Push 1. 3 is not beaten, so it cannot be resolved yet. 1 joins the wait above it.
Top of the stack is 1, the new value is 7. Pop or push?
Answer: Pop 1. 7 beats 1, and it is the first value to do so. That makes it the answer for 1.
Top of the stack is 3, the new value is 7. Pop or push?
Answer: Pop 3. 7 beats 3, and it is the first value to do so. That makes it the answer for 3.
Top of the stack is 4, the new value is 7. Pop or push?
Answer: Pop 4. 7 beats 4, and it is the first value to do so. That makes it the answer for 4.
Top of the stack is 7, the new value is 5. Pop or push?
Answer: Push 5. 7 is not beaten, so it cannot be resolved yet. 5 joins the wait above it.
Top of the stack is 5, the new value is 8. Pop or push?
Answer: Pop 5. 8 beats 5, and it is the first value to do so. That makes it the answer for 5.
Top of the stack is 7, the new value is 8. Pop or push?
Answer: Pop 7. 8 beats 7, and it is the first value to do so. That makes it the answer for 7.
Top of the stack is 8, the new value is 2. Pop or push?
Answer: Push 2. 8 is not beaten, so it cannot be resolved yet. 2 joins the wait above it.
How it runs, step by step
For each value, find the first greater value to its right. Scan left to right. The stack holds values still waiting for their answer, bottom to top.
Finding the next greater element of every value with a stack of values still waiting.
The stack is empty, so nothing is waiting. Push 4.
The stack is empty. 4 is pushed.
3 is not greater than 4, so 4 keeps waiting. Push 3 on top of it.
3 is not greater than the top value 4. 3 is pushed.
1 is not greater than 3, so 3 keeps waiting. Push 1 on top of it.
1 is not greater than the top value 3. 1 is pushed.
7 is greater than 1, so 7 is the next greater element of 1. Pop 1, which now has its answer.
7 is greater than the top value 1. 1 is popped and its answer is 7.
7 is greater than 3, so 7 is the next greater element of 3. Pop 3, which now has its answer.
7 is greater than the top value 3. 3 is popped and its answer is 7.
7 is greater than 4, so 7 is the next greater element of 4. Pop 4, which now has its answer.
7 is greater than the top value 4. 4 is popped and its answer is 7.
The stack is empty, so nothing is waiting. Push 7.
The stack is empty. 7 is pushed.
5 is not greater than 7, so 7 keeps waiting. Push 5 on top of it.
5 is not greater than the top value 7. 5 is pushed.
8 is greater than 5, so 8 is the next greater element of 5. Pop 5, which now has its answer.
8 is greater than the top value 5. 5 is popped and its answer is 8.
8 is greater than 7, so 8 is the next greater element of 7. Pop 7, which now has its answer.
8 is greater than the top value 7. 7 is popped and its answer is 8.
The stack is empty, so nothing is waiting. Push 8.
The stack is empty. 8 is pushed.
2 is not greater than 8, so 8 keeps waiting. Push 2 on top of it.
2 is not greater than the top value 8. 2 is pushed.
The scan is over and 2 values never met a greater value: 8, 2. Their answer stays -1.
The scan is over. 2 values have no greater value to the right: 8, 2.
Answer [7, 7, 7, 8, 8, -1, -1]. Each value was pushed once and popped at most once, 7 pushes and 5 pops for 7 values, so the loop inside the loop is still O(n).
The nearest greater value to the right of each element is [7, 7, 7, 8, 8, -1, -1]. 7 pushes and 5 pops in all.
Write it yourself
Define largestRectangle(values) and return the area of the largest rectangle that fits under the histogram. It runs in your browser against this lesson's own 2 examples.
// Keep bars of increasing height on a stack. When a shorter bar arrives, each bar it pops has found its right edge.function largestRectangle(values) { return 0;}
Remember
- Every value is pushed once and popped at most once, so the nested loop is still O(n).
- Next variants resolve on pop: the value doing the popping is the answer.
- Previous variants resolve on push: after popping, the top is the answer or the stack is empty.
Topics covered
Related
Where this is used
CompilersOperator precedence in expression parsers
Dijkstra's shunting-yard algorithm, published in 1961, keeps an operator stack whose precedence never decreases from bottom to top inside a parenthesis group. An incoming operator pops and emits every stacked operator that binds more tightly, and equal-precedence ones too when the incoming operator is left-associative, which is this pop rule applied to precedence instead of value. The associativity half is where it goes wrong: pop on equal precedence for a right-associative operator and 2^3^2 comes out as (2^3)^2 = 64 instead of 2^(3^2) = 512.
Language runtimesINDENT and DEDENT in Python's tokenizer
CPython's tokenizer holds a stack of indentation columns that strictly increases. A line indented further pushes and emits INDENT, and a line indented less pops and emits one DEDENT per entry removed, stopping when the top matches the new column. The error 'unindent does not match any outer indentation level' is exactly the case where the popping runs past that column and no stacked level equals it.
NetworkingWindowed min and max filters in TCP BBR
BBR needs the largest delivery rate and the smallest RTT seen in a recent window, and the Linux kernel tracks both in lib/win_minmax.c. A new sample that beats a stored candidate makes that candidate worthless forever, since the sample is both better and more recent, so it discards it - the same reasoning that lets the stack pop. The kernel keeps three candidates instead of a full deque, trading exactness for constant space.
Computational geometryConvex hulls by monotone chain
Andrew's monotone chain sorts the points, then walks them keeping a stack of hull vertices and popping any vertex the new point turns the wrong way around. A popped vertex lies inside the hull or flat on one of its edges and can never come back, so the scan costs O(n) after the sort. Graham scan is the same loop with a different sort order, and that is what GEOS runs behind PostGIS ST_ConvexHull: ConvexHull::grahamScan pops the stack while the last two kept points and the new one make a clockwise turn.
Why it works this way
One step can pop almost the whole array, so why is this O(n)?
Look at the whole run, not the worst single step. The while loop at one index can strip nearly the whole stack, but every entry it removes was put there by an earlier index that already paid for it, so the cost is charged at push time and the total is bounded no matter how the pops clump. In 9 8 7 6 10 the first four steps pop nothing and the fifth pops four: that one step is collecting work the earlier steps banked.
< or <= decides what happens to equal values
nextGreater pops while a[top] < a[i], so an equal value never pops and the answer is the next strictly greater element. Flip that to <= and you get the next greater-or-equal, which is a different array. The histogram pops on >= on purpose: an equal bar evicts the earlier one and credits it a width that is too short, but the last bar of the equal run still spans the full width, so the maximum comes out right anyway.
Why the stack holds indices and not values
The value is always one lookup away as a[stack.last()], but a value cannot tell you where it came from. Next-greater needs the index to write the answer into the right slot, and the histogram needs it to measure width. After a pop, read the new top: that is the nearest shorter bar on the left, and because both boundaries are exclusive the rectangle spans i - left - 1 bars, not i - left.
Whatever is left on the stack never found an answer
Those entries were never beaten, so nothing to their right qualifies and next-greater leaves them at -1. The histogram cannot ignore them, because each one still owns a rectangle that runs to the end of the array. One extra iteration with a virtual bar of height 0 pops the stack clean and measures every leftover with its right edge at n, which is why that loop runs 0..h.size and not 0 until h.size.
Read more
- All nearest smaller valuesWikipedia
- Cartesian treeWikipedia
- Stacks and monotonic stacksUSACO Guide
- Nearest Smaller ValuesCSES 1645 · cses.fi
- Largest RectangleHackerRank