Monotonic Stack
The Intuition
You're standing in a crowd at a concert, and everyone wants to know: who's the first person taller than me standing to my right? You could have every person scan right one by one, but that's slow. Here's a better way to think about it.
Imagine people entering a room one at a time from left to right, and they stand on a stack of platforms. When a short person walks in, they step onto the stack. When a tall person walks in, they look at the stack and say "everyone shorter than me, I'm your answer." Those shorter people pop off the stack because they've found their next greater element. And they'll never be the answer for anyone else either, because the tall person is both closer and taller. The tall person then steps onto the stack.
The stack always stays in decreasing order from bottom to top. Why? Because any time a new element would break that order, you pop until the order is restored. Each element gets pushed once and popped once across the entire traversal. That's O(n) total work, not O(n) per element.
After you've processed every element, whatever's left on the stack never found anyone taller to their right. Their answer is -1. The stack handled everything in a single left-to-right pass, and the decreasing order guaranteed that the first element to pop each person off the stack is genuinely the nearest greater one.
Next greater/smaller element, largest rectangle in histogram, trapping rain water, stock span, daily temperatures, or any problem requiring efficient comparison with "nearby" elements.
- Need the K-th greater element (use heap)
- Sliding window min/max (use monotonic queue)
- Need both next greater AND next smaller simultaneously
Variations:
- Monotonic increasing: Stack holds elements in ascending order (useful for next greater element).
- Monotonic decreasing: Stack holds elements in descending order (useful for next smaller element).
- With sentinel values: Adding a zero at the end to flush remaining elements.
- all increasing
- all decreasing
- single element
Key Points
- •Maintain a stack in strictly increasing or decreasing order
- •Pop elements that violate the monotonic property
- •Each element is pushed and popped at most once. Total O(n)
- •Useful for finding next greater/smaller element
- •Can store indices instead of values for more information
Code Template
1 def next_greater_element(arr):
2 """For each element, find the next greater element to its right."""
3 n = len(arr)
4 result = [-1] * n
5 stack = [] # stores indices
6
7 for i in range(n):
8 while stack and arr[i] > arr[stack[-1]]:
9 idx = stack.pop()
10 result[idx] = arr[i]
11 stack.append(i)
12
13 return result
14
15 def largest_rectangle_histogram(heights):
16 """Find largest rectangle in histogram."""
17 stack = []
18 max_area = 0
19 heights.append(0) # sentinel
20
21 for i, h in enumerate(heights):
22 while stack and heights[stack[-1]] > h:
23 height = heights[stack.pop()]
24 width = i if not stack else i - stack[-1] - 1
25 max_area = max(max_area, height * width)
26 stack.append(i)
27
28 heights.pop() # remove sentinel
29 return max_areaCommon Mistakes
- Confusing when to use increasing vs decreasing stack
- Not handling remaining elements in the stack after iteration
- Using values instead of indices when position information is needed