Monotonic Stack Pattern

A monotonic stack keeps values ordered while scanning once.

Typical signals

• next greater/smaller element
• nearest boundary to left/right
• histogram-style area problems

Template

def next_greater(nums):
    stack = []
    ans = [-1] * len(nums)
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            idx = stack.pop()
            ans[idx] = x
        stack.append(i)
    return ans

Practice

• Daily Temperatures
• Largest Rectangle in Histogram