Topic describes

This paper selects LeetCode 239. Maximum sliding window, which is also a frequent question in the interview.

Title description:

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:

Enter: nums = [1.3, -1, -3.5.3.6.7], k = 3Output:3.3.5.5.6.7] the maximum position of the sliding window --------------- ----- [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
Copy the code

Example 2:

Enter: nums = [1], k = 1Output:1]
Copy the code

Example 3:

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

Example 4:

Enter: nums = [9.11], k = 2Output:11]
Copy the code

Example 5:

Enter: nums = [4, -2], k = 2Output:4]
Copy the code

Train of thought

We can maintain the maximum number of sliding Windows in a double-endian queue. Here, we use example 1 to illustrate how the queue processes data, as shown in the figure below:

  • A new element is added, and if it is smaller than the previous one, it is added to the queue
  • Add a new element, if larger than the previous element, remove all values in the window smaller than the new element, and queue
  • Expired elements are removed promptly
  • Keep the maximum sliding window at the end of the queue

Answer key

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number[]}* /
var maxSlidingWindow = function (nums, k) {
  if (nums.length < 2 || k === 1) return nums;
  let dequeue = [],
    res = [];
  for (let i = 0; i < nums.length; i++) {
    // If an expired index is stored in the queue, remove it
    if (i >= k && dequeue[0] <= i - k) {
      dequeue.shift();
    }
    // If the value in the queue is smaller than the current value, it will never be removed
    while (dequeue.length && nums[dequeue[dequeue.length - 1]] <= nums[i]) {
      dequeue.pop();
    }
    // Every time a new number comes in, it must be inserted
    dequeue.push(i);
    // The queue header always stores the maximum value
    if (i >= k - 1) {
      res.push(nums[dequeue[0]]); }}return res;
};
Copy the code

conclusion

One of the tricks used in this problem is to store array subscripts instead of values in the queue to simplify the process of removing expired coordinates

Preliminary review

Leetcode303 area and retrieve | punch brush

LeetCode portfolio combined three clock even | brush

LeetCode data flow of the first 703 K elements | punch brush