This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

Maximum sliding window

Given an integer array numS, there is a sliding window of size K that moves from the leftmost of the array to the rightmost of the array. You can only see k numbers in the sliding window. The slide window moves to the right only one bit at a time to return the maximum value in the slide window.

The monotonous queue

First of all, the elements in the queue must be sorted, and the maximum value must be placed at the queue exit, otherwise how can we know the maximum value? But if you put all the elements in the window into the queue, when the window moves, the queue needs to pop the elements out. The question is, how can the sorted queue eject the element that the window is removing (which may not be the maximum value)?

The queue doesn’t have to maintain all the elements in the window, just the elements that are likely to be the largest in the window, while keeping the values of the elements in the queue from large to small.

Then the queue that maintains the monotonically decreasing elements is called a monotonic queue, that is, a monotonically decreasing or monotonically increasing queue. There is no direct support for monotonic queue in JS, so we need to create a monotonic queue ourselves

Don’t think of the monotonic queue implementation as sorting the numbers in the window. If it does, it’s no different than a priority queue.

Answer key

Create a queue q, deposit is nums subscript I window initialization, the initial k element subscript team, and to ensure the corresponding value is decreasing, if after the previous value is less than a value, then the previous value subscript pop-up So you can guarantee that the q team header element corresponding value, must be the biggest window began to slide in the initial window, Do the same thing we did before. Also, the value subscript outside the window pops up the queue every time you slide, take out the corresponding value of the subscript in the queue header

var maxSlidingWindow = function(nums, k) {
    // Access queue (store element subscript)
    const q = [];
    // Access results
    const ans = [];
    for (let i = 0; i < nums.length; i++) {
        while (q.length && nums[i] >= nums[q[q.length - 1]]) {
            q.pop()
        }
        // Join the current element subscript
        q.push(i);
        // Determine whether the current maximum value (i.e. the first queue element) is in the window, if not, remove it from the queue
        while (q[0] <= i - k) {
            q.shift();
        }
        // Start adding data to the results when the window size is reached
        if (i >= k - 1) ans.push(nums[q[0]])}return ans;
};
Copy the code