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

This article brings two classic sliding window algorithm questions, interested in the console run ~

Maximum sum

Sliding Window: Review the old and learn the New

For example, given the following array: [5, 7, 1, 4, 3, 6, 2, 9, 2], what is the maximum sum of five consecutive elements?

[5, 7, 1, 4, 3] is the first group of five consecutive elements and the sum is 20. [7, 1, 4, 3, 6] is the second group of five consecutive elements and the sum is 21…… In this way, the maximum sum of the five consecutive elements is 24, which is composed of [4, 3, 6, 2, 9].

Here is another way to write this melon, just for reference:

var maxSlidingWindow = function(nums, k) { const sum = function (arr) { return arr.reduce(function(prev, curr, idx, arr){ return prev + curr; }); }; let slidingWindow=nums.slice(0,k) let newSlidingWindow=[] let maxVal; for(let i=k; i<nums.length; i++){ newSlidingWindow=slidingWindow.slice(1).concat(nums[i]) maxVal=Math.max(sum(slidingWindow),sum(newSlidingWindow)) slidingWindow = newSlidingWindow } return maxVal }; const nums= [ 5, 7, 1, 4, 3, 6, 2, 9, 2 ] const k=5 maxSlidingWindow(nums,k) // 24Copy the code

Finding the maximum set

Leetcode-239 (Complex)

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.

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

In this case, the difficulty is marked as: complicated, is it complicated?

  1. Write a function to determine the largest number in an array;
  2. Initialization window, find the maximum save;
  3. Slide window, and then save the maximum value;
  4. Slide until finished;

英 文 解 析 :

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { if(k===1) return nums; // let slidingWindow = nums.slice(0,k) let newSlidingWindow = [] let resArr = [] resarr.push (math.max (... slidingWindow)) for(let i=k; i<nums.length; i++){ newSlidingWindow = slidingWindow.slice(1).concat(nums[i]) resArr.push(Math.max(... newSlidingWindow)) slidingWindow = newSlidingWindow } return resArr };Copy the code

As a result, when the array length is 10 W, an error exceeds the time limit.

Oh! Math.max() is used to find the maximum value from the window at a time of O(n * k), which is still large;

The window is fixed, the maximum value set is basically a monotonous queue problem!

This melon recording screen has a very good animation effect explanation:

Finally, JS solution:

Var maxSlidingWindow = function (nums, k) {const q = []; // result array const ans = []; for (let i = 0; i < nums.length; While (q.length &&nums [I] >= nums[q[q.length-1]]) {q.plop (); } // join the current element subscript q.paush (I); While (q[0] <= i-k) {q.hift (); } // If (I >= k-1) ans. Push (nums[q[0]]); } return ans; };Copy the code

In fact, the sliding window still has a lot of space to expand, even if the window sliding, how to slide, slide after how to do, there is a great difference in the idea of solving the problem!

The above.

I am Anthony Nuggets, the public account of the same name, output exposure input, technical insights into life, see you next time ~~