Maximum sliding window (Item No. 239)

The title

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

link

Leetcode-cn.com/problems/sl…

My own solution

There is no

The reason is very simple, not because of who write their own not to come out, but because of this test is to limit state, there may be many nums, k values may also is very big, there are 5000, so at this time if to maximize operation is likely to lead to an array is beyond time, according to the following this approach is useful when the data quantity is little, but because of its computation time is too long, This can cause problems when there is a large amount of data.

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { var res = [] var window = [] for (let index = 0; index < nums.length; index++) { var item = nums[index] window.push(item) if (window.length > k) { window.shift() } if (window.length >= k) { res.push(Math.max(... window)) } } return res };Copy the code

Better answer 1

/** * @param {number[]} nums * @param {number} k * @return {number[]} */ var maxSlidingWindow = function(nums, k) { var window = [] var res = [] for (let index = 0; index < nums.length ; index++) { if (index - k >= window[0] && index + 1 > k) { window.shift() } while (window.length ! == 0 && nums[window[window.length - 1]] <= nums[index]) { window.pop() } window.push(index) if (index >= k - 1) { res.push(nums[window[0]]) } } return res };Copy the code

Better answer 2

var maxSlidingWindow = function(nums, k) {
    let n = nums.length, p = new Int16Array(n), s = new Int16Array(n), r = new Int16Array(n - k + 1), i = n, j = -1
    while (i--) {
        p[++j] = j % k ? Math.max(p[j - 1], nums[j]) : nums[j]
        s[i]   = i % k ? Math.max(s[i + 1], nums[i]) : nums[i]
    }
    while (i++ < n - k) r[i] = Math.max(s[i], p[i + k - 1])
    return r
}; 

Copy the code

A better answer is 3~N

Leetcode-cn.com/problems/sl…





PS: To view previous articles and titles, click on the links below:

Here are the categories by date 👇

Front end Brush – Table of Contents (date category)

After some friends remind, the feeling should also be classified according to the question type here is classified according to the question type 👇

Front End Brush problem path – Table of Contents (Question type classification)

If you are interested, you can also check out my personal homepage at 👇

Here is RZ