AdvancedData Structures & Algorithms · Lesson 23 of 25 · Updated ·
Monotonic Stack — Next Greater Element, Stock Span and Histograms in O(n)
Many array problems ask, for every element: "what is the next bigger value to my right?" (or the previous smaller one, or how far away it is). Checking every pair is O(n²). A monotonic stack — a stack whose values are always kept in increasing or decreasing order — answers all of them in one pass, O(n).
1. Next greater element
Problem: for each element, print the first value to its right that is strictly greater, or -1 if there is none.
Idea: walk left to right and keep a stack of elements that are still waiting for their next greater value. When a new value x arrives, it is the answer for every waiting element smaller than it — pop them all. Then x waits too.
The waiting elements always form a decreasing stack — anything smaller than a newer element would already have been popped.
def next_greater(a):
ans = [-1] * len(a)
stack = [] # indexes still waiting for an answer
for i, x in enumerate(a):
while stack and a[stack[-1]] < x:
ans[stack.pop()] = x # x is the next greater for that index
stack.append(i)
return ans
print(next_greater([2, 1, 4, 3, 6, 5]))
print(next_greater([5, 4, 3]))
[4, 4, 6, 6, -1, -1]
[-1, -1, -1]
Why O(n)? Each index is pushed once and popped at most once, so the inner while runs at most n times in total — even though it is inside a for.
Store indexes, not values. With the index you can return the value, the distance (i − j) or the position — whatever the problem asks.
2. The four variants
Change two things — the comparison and the direction — and the same loop solves four problems:
| You want | Walk | Pop while the top is… | The stack is |
|---|---|---|---|
| next greater | left → right | smaller than x | decreasing |
| next smaller | left → right | greater than x | increasing |
| previous greater | left → right | ≤ x, then the top is the answer | decreasing |
| previous smaller | left → right | ≥ x, then the top is the answer | increasing |
For the "previous" versions, the answer for x is whatever is left on top after popping.
def previous_smaller(a):
ans, stack = [], []
for x in a:
while stack and stack[-1] >= x:
stack.pop()
ans.append(stack[-1] if stack else -1)
stack.append(x)
return ans
print(previous_smaller([4, 5, 2, 10, 8]))
[-1, 4, -1, 2, 2]
3. Daily temperatures (distance to the next warmer day)
"For each day, how many days until a warmer one? 0 if never." Same loop; store the distance.
def daily_temperatures(t):
ans, stack = [0] * len(t), []
for i, x in enumerate(t):
while stack and t[stack[-1]] < x:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
[1, 1, 4, 2, 1, 1, 0, 0]
4. Largest rectangle in a histogram
The hardest classic. Each bar can be the shortest bar of a rectangle that stretches left and right until a shorter bar blocks it. So for each bar we need its previous smaller and next smaller bar — one increasing stack finds both: when a bar is popped, the bar that pops it is its next smaller, and the bar below it on the stack is its previous smaller.
def largest_rectangle(h):
stack, best = [], 0 # indexes, heights increasing
for i, x in enumerate(h + [0]): # a final 0 pops everything left
while stack and h[stack[-1]] > x:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))
10
4
The answer 10 is the rectangle of height 5 over the bars 5, 6. The sentinel 0 at the end makes sure every bar is popped and measured.
Next greater element in Java
import java.util.*;
public class Main {
static int[] nextGreater(int[] a) {
int[] ans = new int[a.length];
Arrays.fill(ans, -1);
Deque<Integer> stack = new ArrayDeque<>(); // use ArrayDeque, not the old Stack class
for (int i = 0; i < a.length; i++) {
while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
ans[stack.pop()] = a[i];
}
stack.push(i);
}
return ans;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(nextGreater(new int[]{2, 1, 4, 3, 6, 5})));
}
}
[4, 4, 6, 6, -1, -1]
5. How to spot a monotonic stack problem
- The words next / previous greater / smaller, "how many days until", "span", "visible", "nearest taller".
- A brute force with a nested loop that scans left or right until it finds something bigger or smaller.
- Circular arrays (next greater element II): loop over the array twice (
i % n), pushing only during the first pass.
Common mistakes
- Pushing values when you later need positions or distances — push indexes.
- Using
<=instead of<(or the other way round): it decides whether equal values count as "greater". Read the problem. - Forgetting the sentinel (or a final clean-up loop) in the histogram problem, so bars left on the stack are never measured.
- Thinking the nested
whilemakes it O(n²) — it doesn't; count pushes and pops.
Quick recap
- A monotonic stack keeps values in order; elements wait on it until their answer arrives.
- Next greater: pop while the top is smaller than
x; each popped index getsx. - Every index is pushed and popped at most once: O(n) time, O(n) space.
- Same pattern: next/previous smaller, daily temperatures, stock span, largest rectangle.