Topic describes

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 sliding window moves only one bit to the right at a time.

Returns the maximum value in the sliding window.

Example 1:

Input: nums = [1, 3, 1, 3,5,3,6,7], k = 3 output:,3,5,5,6,7 [3] : The position of the sliding window Maximum -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- [1] 3-1-3 3 5 6 7 3 1 [3-1-3] 3 5 6 7 3 1 3 [1-3-5] 3 6 7 5 3-1/3-3 5 6 7 5 1 3 1-3 [5 3 6] 7 6 1 3 1-3 5 [3 6 7] 7Copy the code

Example 2:

Input: nums = [1], k = 1Copy the code

Example 3:

Input: nums = [1,-1], k = 1Copy the code

Example 4:

Input: nums = [9,11], k = 2 output: [11]Copy the code

Example 5:

Input: nums = [4,-2], k = 2 output: [4]Copy the code

Tip:

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

Thinking on

There are two main ways to do this. The first way is to use the extension operator to extract all the values in the window, then use math.max to find the maximum value, and add that maximum value to the Result array. But this approach may run out of time.

The second approach is to use a double-ended queue (the queue can be entered or left on both sides) that stores the subscript of the value in the window, ensuring that the window header element is always the maximum value of the window

Subscript of currently entering element – subscript >= k of window header element removed from queue

If the current number is greater than the end of the queue, the end of the queue is removed until the current number is less than or equal to the end of the queue, or the queue is empty (ensure that the values on the left of the window are greater than the current value of the queue, this will ensure that the next loop window header elements out of the queue, the window header element is still the maximum)

Queue elements are queued

Start adding the maximum value to the result after the KTH iteration

AC code

Method one:

var maxSlidingWindow = function(nums, k) {
    if (k <= 1) return nums;
    const res = [];
    for (let i = 0; i < nums.length - k + 1; ++i) {
        res.push(Math.max(... nums.slice(i, i + k))); }return res;

};
Copy the code

Method 2:

var maxSlidingWindow = function (nums, k) {
    const window = [];
    const result = [];
    for (let i = 0; i < nums.length; i++) {
      if (i - window[0] > k - 1) {
        window.shift();
      }
      let j = window.length - 1;
      while (j >= 0 && nums[window[j]] <= nums[i]) {
        j--;
        window.pop();
      }
      window.push(i);
      if (i >= k - 1) {
        result.push(nums[window[0]]); }}return result;
  };
Copy the code

conclusion

The second solution uses a double-ended queue, ensuring that the first element in the window queue is the largest element in the queue. If the new element is larger than the previous element, the queue pops out. Each time the window moves back one bit, the head element of the queue is pushed into the Result array.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign