239. Sliding Window Maximum

Given an array nums and a window size k that slides from left to right one step at a time, return the maximum of each window.

Keep a deque of indices whose values are strictly decreasing. A new value evicts smaller values from the back (they can never be a max again). The front is the window max; drop it once it slides out.

1function maxSlidingWindow(nums: number[], k: number): number[] {
2  const dq: number[] = [], res: number[] = [];
3  for (let i = 0; i < nums.length; i++) {
4    while (dq.length && nums[dq.at(-1)!] <= nums[i]) dq.pop();
5    dq.push(i);
6    if (dq[0] <= i - k) dq.shift();
7    if (i >= k - 1) res.push(nums[dq[0]]);
8  }
9  return res;
10}

nums

-1

-3

deque (indices, values decreasing)

empty

result

empty

i = 0, nums[i] = 1.

1 / 0

Space: play/pause · ←/→: step