Sliding Window Maximum

You are given an integer array nums. A sliding window of size k moves from the leftmost side of the array to the right, one element at a time. You can only see k numbers in the window. The sliding window moves one step to the right each time.

Return the maximum sliding window.

Example

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
Input: nums = [1], k = 1 Output: [1]
Input: nums = [1,-1], k = 1 Output: [1,-1]
Input: nums = [9,11], k = 2 Output: [11]

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
    const indexGroup = [], maxGroup = [];
    nums.forEach((v,i) => {
        if(i >= k && indexGroup[0] <= i-k) indexGroup.shift();
        while(indexGroup && nums[indexGroup[indexGroup.length-1]] <= v) indexGroup.pop();
        indexGroup.push(i);
        if(i >= k-1) maxGroup.push(nums[indexGroup[0]]);
    })
    return maxGroup;
};

// Normal approach times out and needs optimization
// var maxSlidingWindow = function(nums, k) {
//     const maxGroup = [];
//     for(let i=0,n=nums.length; i<=n-k; ++i){
//         maxGroup.push(Math.max(...nums.slice(i, i+k)));
//     }
//     return maxGroup;
// };

Solution

The brute force approach won't work, it times out. We need to optimize the approach. In fact, for two adjacent sliding windows, they share k-1 elements, and only 1 element changes. We can optimize based on this characteristic. We can maintain a monotonic decreasing window. When moving to the right, we pop the values from the left side of the window that exceed the window size because only the window's maximum value is needed. We only need to ensure that the values within the window are decreasing, meaning that if a new value is added, all smaller existing values are popped. The leftmost value is the maximum in the window. First, we define a window to store the indices of the decreasing values, and an array to store the maximum values. Then, we iterate through the given array. If the current index is greater than or equal to the window size and the first value in the decreasing index window is outside the current window, we pop it. Then, we traverse backward, and if there is a value in the decreasing window and it is less than the value about to be added, we pop it. Finally, if the window can form k elements, we start to take the maximum value, which is the first value of the decreasing window, and add it to the maximum value array. After the loop ends, we return the maximum value array.

Daily Challenge

https://github.com/WindrunnerMax/EveryDay

Reference

https://leetcode-cn.com/problems/sliding-window-maximum/