Monotonic Stack & Queue Patterns

Why this module exists

Monotonic structures give you O(n) solutions for problems that look like nested loops. The core idea: keep a stack or deque in sorted order so each index is pushed and popped at most once.

Monotonic stack (next greater / smaller)

Maintain a stack of indices with decreasing values.

When you see a larger value, pop until the stack is valid. Each popped index has just found its next greater element.

func nextGreater(nums []int) []int {
    n := len(nums)
    res := make([]int, n)
    for i := range res {
        res[i] = -1
    }
    stack := []int{}
    for i, v := range nums {
        for len(stack) > 0 && nums[stack[len(stack)-1]] < v {
            j := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            res[j] = v
        }
        stack = append(stack, i)
    }
    return res
}

Largest rectangle in histogram

Keep a stack of increasing heights. When a new bar is lower, pop and compute the rectangle with the popped height as the limiting height.

Key trick: append a sentinel height 0 to flush the stack at the end.

Monotonic deque (sliding window max)

For a window of size k:

• Pop from back while new value is larger
• Pop from front if it is outside the window
• Front is always the maximum

This gives O(n) total time for all windows.

What you will build

• Next greater element with a monotonic stack.
• Largest rectangle in a histogram using stack boundaries.