Monotonic Stack and Deque

A monotonic stack keeps its values sorted (increasing or decreasing) by popping any that violate the order before each push. Store indices, not values, so you can write into the right slot and measure distances. Every element is pushed once and popped at most once, so a while inside a for is still O(n) — that is the amortized argument.

Next greater element (canonical)

• For each item, first strictly larger value to its right (-1 if none).
• Walk left to right; stack holds indices whose answer is still pending, values decreasing bottom to top.
• Current value resolves every smaller pending index on top: pop it and record the answer, then push the current index.
• Seed answer with the sentinel; whatever stays on the stack at the end never found a larger value.

def next_greater(nums: list[int]) -> list[int]:
    answer = [-1] * len(nums)
    stack: list[int] = []          # pending indices
    for i in range(len(nums)):
        while stack and nums[stack[-1]] < nums[i]:
            answer[stack.pop()] = nums[i]
        stack.append(i)
    return answer
# next_greater([2,1,2,4,3]) -> [4,2,4,-1,-1]

• Distances instead of values: write i - j on pop (e.g. “days until warmer”). Indices make this trivial; stored values cannot.
• Previous smaller (mirror): increasing stack, pop top while >= current, read surviving top before pushing.

Largest rectangle in a histogram

• Increasing stack of indices; append a trailing 0 to flush. When a shorter bar arrives, pop the top: height = heights[top], width = i - (stack[-1] if stack else -1) - 1, update best. Each index pushed/popped once -> O(n) time, O(n) space.

Monotonic deque: sliding-window maximum

• Fixed window k; use collections.deque of indices, values decreasing front -> back.
• Back: pop while nums[back] <= nums[i], then append i.
• Front: pop if dq[0] <= i - k (left the window).
• Front index is the window max; record once i >= k - 1. O(n) time, O(k) space.

from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()   # indices, values decreasing front -> back
    out: list[int] = []
    for i in range(len(nums)):
        while dq and nums[dq[-1]] <= nums[i]:   # back: drop smaller
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:                      # front: drop expired
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out
# max_sliding_window([1,3,-1,-3,5,3,6,7], 3) -> [3,3,5,5,6,7]

Pitfalls

• Storing values, not indices — kills distance and window-expiry logic.
• Strict vs non-strict: pop on < for strictly-greater, on <= in the deque so equals replace older copies.
• Read answer on pop (next-greater) vs before push (previous-smaller) — don’t mix the timing.
• Flush pending items: seed the sentinel or append one.
• Deque expiry is dq[0] <= i - k; off-by-one keeps a stale index.

Summary table