Sliding Window Maximum | Problems

Given an array and window size k, return the max value in each sliding window.

Example: nums = [1,3,-1,-3,5,3,6,7], k = 3 → Output: [3,3,5,5,6,7]

Sample Input

—

Sample Output

—

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

Test Cases

Case 1

Args: [[1,3,-1,-3,5,3,6,7],3] Expected: [3,3,5,5,6,7]

Topics

Heap Priority Queue

Monotonic Deque

function maxSlidingWindow(nums, k) {
  const deque = [], 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;
}

Time: O(n) | Space: O(k)

Saved in this browser only. Private to you.