Monotonic Stack
DSA · Stacks and Queues
Theory
A monotonic stack keeps its elements in increasing or decreasing order. When a new element would break the order, elements are popped until the order is restored; at that moment each popped element has found its "next greater" (or smaller) element. Every element is pushed and popped at most once, so the whole scan is O(n).
Why we use it
It answers "next greater/smaller element" style questions in linear time instead of O(n²).
When to use it
Use it for next greater element, daily temperatures, stock span, largest rectangle in a histogram, and trapping rain water.
How it works
- For each element x
- Stack not empty and top < x? Yes: Pop top: x is its next greater element. No: Push x.
- Repeat the check
- Remaining items have no next greater element
Syntax
stack = [] # holds indexes
for i, x in enumerate(arr):
while stack and arr[stack[-1]] < x:
j = stack.pop(); answer[j] = x # next greater for j
stack.append(i)Example
def next_greater(nums):
answer = [-1] * len(nums)
stack = []
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
answer[stack.pop()] = nums[i]
stack.append(i)
return answer
def days_until_warmer(temps):
wait = [0] * len(temps)
stack = []
for i in range(len(temps)):
while stack and temps[stack[-1]] < temps[i]:
j = stack.pop()
wait[j] = i - j
stack.append(i)
return wait
print(next_greater([4, 5, 2, 25, 7, 8]))
print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))Key points
- Stack stays sorted
- Each element pushed and popped once: O(n)
- Solves next greater/smaller problems
- Store indexes to compute distances