Monotonic Stack

Back to Index

Use when: next greater/smaller element, largest rectangle in histogram, trapping rain water, stock span.

Signal words: next greater, previous smaller, largest rectangle, temperature span.

Core Idea

Maintain a stack where elements are always in monotonically increasing (or decreasing) order. When a new element breaks the ordering, pop and process those elements.

Next Greater Element (monotonic decreasing stack)

stack = []  # stores indices
result = [-1] * len(nums)
 
for i, num in enumerate(nums):
    while stack and nums[stack[-1]] < num:
        idx = stack.pop()
        result[idx] = num  # num is the next greater for nums[idx]
    stack.append(i)
return result

Next Smaller Element (monotonic increasing stack)

Same pattern, flip the comparison: nums[stack[-1]] > num.

Key Insight

The element that causes a pop IS the answer for everything being popped. Think: “what event resolves pending questions on the stack?”

---

Problems Using This Pattern