Stacks and Monotonic Stacks

Matching and next greater element

A stack (Python list with append/pop) handles nested structure: matching brackets, evaluating expressions, undo history. A monotonic stack keeps indices with decreasing (or increasing) values; when a larger value arrives, it resolves every smaller pending index at once. This solves "next greater element", "daily temperatures", stock spans and the largest rectangle in a histogram in O(n).

Daily temperatures and valid brackets, run

I ran this with Python 3.12.3 (standard library only). Each day gets the number of days until a warmer one (0 if none); bracket validation fails for wrong nesting and unclosed brackets.

# Monotonic stack: days until a warmer temperature
def daily_temperatures(temps):
    res, stack = [0] * len(temps), []    # stack of indices with decreasing temps
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

# Valid parentheses with a plain stack
def valid(s):
    pairs, stack = {")": "(", "]": "[", "}": "{"}, []
    for ch in s:
        if ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
print([valid(s) for s in ("()[]{}", "([)]", "{[]}", "((")])

Output:

[1, 1, 4, 2, 1, 1, 0, 0]
[True, False, True, False]

Check the empty stack

Popping an empty stack is the classic bug; handle a closing bracket with nothing open.

Quick check: Which pattern finds the next greater element for every position in O(n)?

• A min-heap
• A monotonic stack
• Binary search on each element
• Sorting the array