Sliding Window Maximum

Problem

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation: 
Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴
1 <= k <= nums.length

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const res = [];
    const dequeue = []; // sorted in ascending order by value and index
    let l = -k + 1; // left of window
    let r = 0; // right of window

    for (; r < nums.length; r++, l++) {
        // remove all elements from the back that are less then our current element
        while (dequeue[dequeue.length - 1]?.val < nums[r]) {
            dequeue.pop();
        }

        // remove all elements from the front that are no longer in our window
        while (dequeue[0]?.i < l) {
            dequeue.shift();
        }

        // push current element and push max of current window
        dequeue.push({ val: nums[r], i: r });
        if (l >= 0) { // if l is valid
            res.push(dequeue[0].val);
        }
    }
    return res;
};

We will implement a sliding window solution. We use l and r to represent the start and end index of our window respectively (such that the window size is always k). In addition, we use a double ended queue dequeue to store partial elements in the index range of [l, r] so that they are sorted in ascending order by value and index. This can be done through two steps (during each iteration):

Remove all elements from the back of dequeue that has value less then our current element (this ensures dequeue is sorted in ascending order by value).
Remove all elements from the front of dequeue that are no longer in our window (this ensures all elements in dequeue are in [l, r]).

Note that dequeue is implicitly sorted by index. Thus, it is easy to see that the max value of each window is the first value in dequeue.

Problem​

Solution​

Problem

Solution