Stage 4: Advanced Techniques·Monotonic Stack & Deque

Hard#2399 min readMonotonic DequeSliding WindowLeetCode

Sliding Window Maximum

Monotonic deque

Monotonic deque. Maintain decreasing order; front is always the max.

Published Apr 16, 2026

Problem

Given an integer array nums and a window size k, return the maximum of each size-k sliding window as you slide from left to right.

There are n - k + 1 windows in total.

Input

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Output

[3, 3, 5, 5, 6, 7]

Explanation

Window [1,3,-1] → 3. [3,-1,-3] → 3. [-1,-3,5] → 5. [-3,5,3] → 5. [5,3,6] → 6. [3,6,7] → 7.

Input

nums = [1], k = 1

Output

[1]

Input

nums = [9, 11], k = 2

Output

[11]

Intuition

The naive version scans each window in O(k) time — O(nk) total. That's too slow when n and k both reach 10^5.

A heap gets you to O(n log k): push the new element, lazily pop stale indices off the top. Fast enough for many problems but still carries a log factor and an allocation-heavy payload.

The strict linear answer is a monotonic decreasing deque of indices. We keep only indices whose values could ever become the max of a future window:

If a brand-new index has a larger value, every smaller index still sitting in the deque is now useless — no future window containing the new index will ever pick them. Pop them from the back.
If the index at the front has fallen out of the window, remove it from the front.

At every step, the max of the current window is nums[deque.front()]. Each index enters and leaves the deque at most once, so the amortized work per step is O(1).

Approach

Brute Force

TimeO(n · k)

SpaceO(1)

Slide a window; for each position, linearly scan the window and take the max. Correct and obvious; doesn't scale.

impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = nums.len();
        let mut out = Vec::with_capacity(n - k + 1);

        for i in 0..=(n - k) {
            let mut m = nums[i];
            for j in (i + 1)..(i + k) {
                if nums[j] > m {
                    m = nums[j];
                }
            }
            out.push(m);
        }

        out
    }
}

Rust · runnable

function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  const out: number[] = [];

  for (let i = 0; i + k <= n; i++) {
    let m = nums[i];
    for (let j = i + 1; j < i + k; j++) {
      if (nums[j] > m) m = nums[j];
    }
    out.push(m);
  }

  return out;
}

TypeScript · runnable

Max-Heap with Lazy Deletion

TimeO(n log k)

SpaceO(n)

Push every (value, index) into a max-heap. Before reading the top, pop anything whose index is outside the current window. When the top is in-window, record it as the window's answer.

The heap can grow to n because we never eagerly delete — only lazily when a stale entry surfaces. Still O(n log k) amortized because each element pushes once and pops at most once.

use std::collections::BinaryHeap;

impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = nums.len();
        let mut heap: BinaryHeap<(i32, usize)> = BinaryHeap::with_capacity(n);
        let mut out = Vec::with_capacity(n - k + 1);

        for i in 0..n {
            heap.push((nums[i], i));

            if i + 1 >= k {
                let left = i + 1 - k;
                while let Some(&(_, j)) = heap.peek() {
                    if j < left {
                        heap.pop();
                    } else {
                        break;
                    }
                }
                out.push(heap.peek().unwrap().0);
            }
        }

        out
    }
}

Rust · runnable

function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  // Binary max-heap keyed on value, breaking ties by index.
  const heap: Array<[number, number]> = [];
  const less = (a: [number, number], b: [number, number]) =>
    a[0] < b[0] || (a[0] === b[0] && a[1] < b[1]);

  const push = (node: [number, number]) => {
    heap.push(node);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (less(heap[p], heap[i])) {
        [heap[p], heap[i]] = [heap[i], heap[p]];
        i = p;
      } else break;
    }
  };
  const pop = () => {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
      heap[0] = last;
      let i = 0;
      const n2 = heap.length;
      while (true) {
        const l = 2 * i + 1;
        const r = 2 * i + 2;
        let best = i;
        if (l < n2 && less(heap[best], heap[l])) best = l;
        if (r < n2 && less(heap[best], heap[r])) best = r;
        if (best !== i) {
          [heap[best], heap[i]] = [heap[i], heap[best]];
          i = best;
        } else break;
      }
    }
    return top;
  };

  const out: number[] = [];
  for (let i = 0; i < n; i++) {
    push([nums[i], i]);
    if (i + 1 >= k) {
      const left = i + 1 - k;
      while (heap.length > 0 && heap[0][1] < left) pop();
      out.push(heap[0][0]);
    }
  }

  return out;
}

TypeScript · runnable

Monotonic Deque

TimeO(n)

SpaceO(k)

Recommended

Maintain a deque of indices such that the values at those indices are strictly decreasing from front to back.

For each i:

Evict stale front. If the front index < i - k + 1, pop it.
Shrink from back. While the back index's value is <= nums[i], pop it. Those values cannot be the max of any window that also contains i.
Push i at the back.
Once i >= k - 1 we have a full window; emit nums[deque.front()].

Each index enters and leaves the deque at most once, so the total work is O(n).

use std::collections::VecDeque;

impl Solution {
    pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let k = k as usize;
        let n = nums.len();
        let mut dq: VecDeque<usize> = VecDeque::with_capacity(k);
        let mut out = Vec::with_capacity(n - k + 1);

        for i in 0..n {
            // Evict stale front.
            while let Some(&front) = dq.front() {
                if i >= k && front + k <= i {
                    dq.pop_front();
                } else {
                    break;
                }
            }

            // Shrink from the back while smaller-or-equal.
            while let Some(&back)= dq.back() {
                if nums[back] <= nums[i] {
                    dq.pop_back();
                } else {
                    break;
                }
            }

            dq.push_back(i);

            if i + 1 >= k {
                out.push(nums[*dq.front().unwrap()]);
            }
        }

        out
    }
}

Rust · runnable

function maxSlidingWindow(nums: number[], k: number): number[] {
  const n = nums.length;
  const dq: number[] = [];
  const out: number[] = [];

  for (let i = 0; i < n; i++) {
    // Evict stale front.
    if (dq.length > 0 && dq[0] + k <= i) {
      dq.shift();
    }

    // Shrink from the back while smaller-or-equal.
    while (dq.length > 0 && nums[dq[dq.length - 1]] <= nums[i]) {
      dq.pop();
    }

    dq.push(i);

    if (i + 1 >= k) {
      out.push(nums[dq[0]]);
    }
  }

  return out;
}

TypeScript · runnable

A few notes:

Strict <= for back-eviction — keeping equal values doesn't help; dropping the older one is free because we'd have to drop it first anyway.
Indices, not values — without the index we can't detect when the front has slid out of the window.
shift() is O(n) in JS for large deques. In tight real-time loops, swap for a circular buffer or a head pointer.

Trace

Monotonic deque walking nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3:

i	x	evict front	pop back	dq after	emit
0	1	—	—	[0]	—
1	3	—	pop 0 (1≤3)	[1]	—
2	-1	—	—	[1, 2]	3
3	-3	—	—	[1, 2, 3]	3
4	5	pop 1	pop 3, pop 2	[4]	5
5	3	—	—	[4, 5]	5
6	6	—	pop 5, pop 4	[6]	6
7	7	—	pop 6	[7]	7

Final answer: [3, 3, 5, 5, 6, 7].

Edge cases

k = 1 — every window is a single element; the deque holds one index at a time; output equals input.
k = n — single window; the deque ends up containing only indices of the running maximum; output is a one-element array with the global max.
Monotonically increasing nums — every new value pops the entire deque before pushing itself. Amortized linear because every index pops at most once.
Monotonically decreasing nums — nothing pops from the back; the front eviction handles window slides. Deque can grow to size k.

💡

Tip

The monotonic deque is the sliding-window cousin of the monotonic stack. Stack = "next greater / smaller on unbounded tail". Deque = "next greater / smaller bounded by a moving window." Same pop-on-condition logic, plus one front eviction.

Takeaway

Whenever a problem asks "what's the max (or min) of the last k values as a window slides," a monotonic deque erases the log factor that a heap would charge.

Production-side, this is exactly how low-latency trading systems maintain rolling extrema over order-book snapshots — the heap's branch-heavy reheap is what the deque buys you out of.

Easy#496

Next Greater Element I

The basic pattern. Process right to left, stack holds candidates.

Medium#503

Next Greater Element II

Circular array — iterate twice through the array.

Hard#76

Minimum Window Substring

The ‘hard’ sliding window — but if you understood #3, this is the same pattern with a counter.