Monotonic stack - the pattern that blew my mind

Once I understood monotonic stacks, I couldn't believe how many problems it simplifies:

What it is: A stack that maintains elements in strictly increasing or decreasing order.

Problems it solves:

• Next Greater Element (the classic)
• Daily Temperatures
• Largest Rectangle in Histogram
• Trapping Rain Water
• Stock Span Problem
• Remove K Digits

The template:

stack = []
for i, num in enumerate(arr):
    while stack and condition(stack[-1], num):
        # Process the popped element
        stack.pop()
    stack.append(i)  # or (i, num)

The key insight: elements that will never be needed again get popped immediately, keeping the stack useful.

This pattern is asked in ~5% of all coding interviews. Worth learning!