滑动窗口的最大值-239

[sl1673495]

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

  滑动窗口的位置                最大值
---------------               -----
[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

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤  输入数组的大小。

注意：本题与主站 239 题相同：https://leetcode-cn.com/problems/sliding-window-maximum/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

滑动窗口，每次左右各滑动一位，并且求窗口中的最大值记录即可，这题坑的地方在于边界情况比较多。

let maxSlidingWindow = function (nums, k) {
  if (k === 0 || !nums.length) {
    return []
  }
  let left = 0
  let right = k - 1
  let res = [findMax(nums, left, right)]

  while (right < nums.length - 1) {
    right++
    left++
    res.push(findMax(nums, left, right))
  }

  return res
}

function findMax(nums, left, right) {
  let max = -Infinity
  for (let i = left; i <= right; i++) {
    max = Math.max(max, nums[i])
  }
  return max
}

[vortesnail]

单调队列实现：

let maxSlidingWindow = function (nums, k) {
  const res = [];
  const queue = [];
  for (let i = 0; i < nums.length; i++) {
    if (i - k >= queue[0]) {
      queue.shift();
    }
    while (nums[queue[queue.length - 1]] <= nums[i]) {
      queue.pop();
    }
    queue.push(i);

    if ((i + 1) >= k) {
      res.push(nums[queue[0]]);
    }
  }
  return res;
};

[cwjbjy]

滑动窗口

var maxSlidingWindow = function (nums, k) {
    let len = nums.length, res = [];
    if (k == 0 || len == 0) {
        return res
    }
    let left = 0, right = k - 1;
    while (right < len) {
        let max = Math.max(...nums.slice(left, right + 1))
        res.push(max)
        left++;
        right++;
    }
    return res
};