剑指 Offer 59 - I. 滑动窗口的最大值

剑指 Offer 59 - I. 滑动窗口的最大值

给定一个数组 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/

思路

暴力

双重循环求每一个窗口的最大值

单调队列

使用一个队列单调队列存储元素。遍历时，先判断移动窗口后被丢弃的那个元素是不是和队首的元素相同，是的话说明该元素已经不在窗口内，直接出队。再将新进入的元素加入单调队列中（如果当前队尾元素比当前元素小直接移除，保持队列单调递减）。再将队首加入结果数组中。

解答

暴力

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

单调队列

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  if (!nums.length) return [];
  if (k === 1) return nums;
  const res = [];
  let queue = [];
  for (let i = 0; i < nums.length; i++) {
    if (i >= k) {
      let outElem = nums[i - k];
      if (outElem === queue[0]) queue.shift();
    }
    const inItem = nums[i];
    while (queue.length && queue[queue.length - 1] < inItem) queue.pop();
    queue.push(inItem);
    if (i >= k - 1) res.push(queue.slice(-k)[0]);
  }
  return res;
};