Monotonic deque (sliding window max/min)

O(n)

Store indices in a double-ended queue kept decreasing (or increasing) in value; drop indices that fell out of the window from the front, and drop indices beaten by the new value from the back, so the front is always the current window's max (or min).

Signals

maximum or minimum of every window of size ksliding window maximum/minimumshortest subarray with a sum at least Kneed both ends of a queue popped/pusheddeque, double-ended queue

Template

function maxSlidingWindow(nums, k) {
    const deque = []; // stores indices, values decreasing
    const result = [];
    for (let i = 0; i < nums.length; i++) {
        while (deque.length && deque[0] <= i - k) deque.shift();
        while (deque.length && nums[deque[deque.length - 1]] < nums[i]) deque.pop();
        deque.push(i);
        if (i >= k - 1) result.push(nums[deque[0]]);
    }
    return result;
}

Looks similar, isn't

Sliding window (fixed): A plain fixed window recomputes the sum incrementally in O(1) per step, but finding the window's max/min that way costs O(k) per step (O(nk) total) if you rescan. The monotonic deque gives every window's max/min in total O(n) by never re-examining a beaten value.
Monotonic stack: A monotonic stack only ever pops from one end (the top). Here you need to expire old indices from the front as the window slides AND pop beaten values from the back, which needs both ends, hence a deque, not a single-ended stack.

n up to 1e5 elements, window size k -> O(n): each index enters and leaves the deque at most once, total work is linear regardless of k.

Learn this pattern