Monotonic Stack

Next greater element, histograms and stock spans in O(n).

A monotonic stack keeps its elements in sorted order (increasing or decreasing). Each new element pops everything it "beats", and those pops are where the answers come from. It turns many O(n²) "look left/right for the next bigger thing" problems into O(n).

When to use it

Next greater / next smaller element (to the right or left)
"How many days until a warmer temperature?"
Largest rectangle in a histogram, maximal rectangles
Stock span, trapping rain water
Removing digits to make the smallest number

Template: next greater element

Keep a stack of indices whose answer is still unknown, with values decreasing from bottom to top. When a bigger value arrives, it's the answer for everything smaller on the stack.

def next_greater(nums):
    result = [-1] * len(nums)
    stack = []                       # indices, values decreasing
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x
        stack.append(i)
    return result

Daily temperatures is the same loop with result[j] = i - j (distance instead of value).

Why it's O(n)

The inner while loop looks quadratic, but every index is pushed once and popped at most once, so the total work across the whole loop is O(n). Mention this amortized argument when you state the complexity.

Choosing the direction

For "previous greater/smaller", the answer for the current element is whatever remains on top after popping.

Largest rectangle in a histogram

Maintain an increasing stack of bar indices. When a shorter bar arrives, each popped bar's rectangle extends from the new stack top + 1 to the current index − 1:

def largest_rectangle(heights):
    stack, best = [], 0
    for i, h in enumerate(heights + [0]):    # sentinel flushes the stack
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

[!TIP] Practice Daily Temperatures · Trapping Rain Water