Monotonic Stack / Queue

Keep it ordered

A monotonic stack only pushes elements that keep the stack increasing (or decreasing). Before pushing, pop everything that violates the order. Each element is pushed and popped at most once, giving O(n) total for problems that look O(n^2) at first glance.

Next greater element

Scan right to left (or left to right with indices). Pop smaller elements before pushing — whoever remains on top is the next greater.

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

Output:

next_greater([2, 1, 2, 4, 3])
# [4, 2, 4, -1, -1]

Sliding window maximum

A monotonic deque of indices keeps the window's max at the front. Drop indices that fall out of the window, and pop smaller trailing values before appending.

from collections import deque

def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Spot the pattern

Reach for a monotonic stack/queue for: next greater/smaller element, largest rectangle in histogram, sliding window max/min, and stock-span style problems.