You have an array and a sliding window of size k. As the window moves one position to the right, you need to report the maximum value in the current window. For [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the window maxima are [3, 3, 5, 5, 6, 7].
Unlike sum — where you can subtract the departing element and add the arriving one — maximum doesn't have a clean “undo” operation. If the current max leaves the window, you can't derive the new max from the old one. You'd need to rescan the entire window.
The brute force rescans k elements for each of the n - k + 1 window positions. That's O(n * k). For n = 100,000 and k = 10,000, that's a billion operations.
A monotonic stack can find “next greater to the right” in O(n). But the sliding window adds a constraint the stack can't handle: expiration. The maximum candidate might have entered the structure long ago and is no longer inside the current window. The stack only removes elements from one end — it has no way to evict from the bottom.
The stack needs a second door.
A deque (double-ended queue) supports insertion and removal from both ends. This is exactly what the sliding window maximum needs: one end for maintaining monotonicity (just like the stack), and the other end for expiring elements that have left the window.
Here's the strategy. Maintain a monotonically decreasing deque of indices. The front of the deque always holds the index of the current window maximum. Two rules govern the deque:
Rule 1 — Dominance eviction (back): When a new element arrives, remove all indices from the back of the deque whose corresponding values are smaller than or equal to the new element. These elements can never be the window maximum — the new element is bigger AND entered more recently, so it will outlast them in the window.
Rule 2 — Expiry eviction (front): Before reading the maximum, check if the front of the deque has fallen outside the window. If deque.front() <= i - k, remove it. It's expired.
Dominance eviction is the familiar monotonic stack operation — pop smaller elements from the top. Expiry eviction is the new operation that the deque makes possible — remove from the front when an element ages out.
Watch both rules in action. As each element enters the window, it may trigger dominance evictions from the back. As the window slides past an element, it may trigger an expiry eviction from the front.
The front of the deque is always the current window max. Pay attention to which rule fires and when — they never conflict, but they serve completely different purposes.
Tap each cell to scan for the maximum in window 1.
Here's the full implementation. Note how compact it is — the two rules are each a single while or if:
function maxSlidingWindow( nums: number[], k: number): number[] { const deque: number[] = []; // indices, front = max const result: number[] = []; for (let i = 0; i < nums.length; i++) { // Rule 1: dominance — evict smaller from back while ( deque.length && nums[deque.at(-1)!] <= nums[i] ) { deque.pop(); } deque.push(i); // Rule 2: expiry — evict old from front if (deque[0] <= i - k) { deque.shift(); } // Window is full, record the max if (i >= k - 1) { result.push(nums[deque[0]]); } } return result;}The deque stores indices, not values — just like the monotonic stack. Indices let you check whether an element has expired (deque[0] <= i - k) without needing a separate timestamp.
Each element enters the deque once and leaves once (either through dominance eviction or expiry). Total operations: 2n. Time complexity: O(n). The O(n * k) rescan is gone.
The monotonic deque is a generalization of the monotonic stack. The stack answers “for each element, find the nearest element satisfying a comparison.” The deque answers “within a sliding window, maintain an extremum efficiently.”
Any time you see a sliding window combined with min or max queries, the monotonic deque is your tool. Classic problems:
k states; the deque makes it O(n) instead of O(n * k)The mental model: a monotonic deque is a queue with an opinion. It accepts elements at the back, evicts losers from the back (dominance), and retires old winners from the front (expiry). The front is always the current answer. Two doors, two rules, O(1) amortized access to the window extremum.
That's the full monotonic stack module. From the basic “who answers whom” model, through amortized analysis, variant selection, histogram boundaries, and finally the deque extension. One data structure, five problems, one unifying idea: maintain an ordering invariant, and the moments of violation are the moments of discovery.