Monotonic Stack
A monotonic stack is just a stack that maintains elements in sorted order (either increasing or decreasing). It's surprisingly powerful for a simple idea - it lets you find the "next greater" or "next smaller" element for every position in O(n) time.
The Core Idea
As you iterate through an array, maintain a stack where elements are always in order. When a new element would break the order, pop elements until it doesn't. Those popped elements just found their answer!
When you pop an element from a monotonic stack, you've found the relationship you were looking for. The current element is the "next greater" (or smaller) for everything being popped.
Classic: Next Greater Element
For each element, find the next element to the right that's larger:
def nextGreater(nums):
n = len(nums)
result = [-1] * n
stack = [] # Indices
for i, num in enumerate(nums):
while stack and nums[stack[-1]] < num:
idx = stack.pop()
result[idx] = num # Found it!
stack.append(i)
return resultClassic: Largest Rectangle in Histogram
Find the largest rectangular area in a histogram:
def largestRectangle(heights):
stack = []
max_area = 0
heights.append(0) # Sentinel
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_areaWhen to Use Monotonic Stack
- Next greater/smaller element - The classic use case
- Previous greater/smaller element - Same idea, different direction
- Histogram problems - Find max rectangle
- Stock span problems - How many consecutive days
- Trapping rain water - Find boundaries
Store indices in the stack, not values. You can always look up the value, but you need the index to calculate distances and update result arrays.