题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例 1：

  输入：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

解题方案

• 标签：单调队列
• 整体思路：
  • 从题目上来看是用过维护滑动窗口，然后每次求滑动窗口中的最大值即可，设置数组的长度为n,窗口的长度为k,则时间复杂度为 O(k*(n-k+1)) = O(kn)
  • 很显然使用暴力解法的话，时间复杂度会随着k的变大不断的变大，而其中有很多元素在不同的滑动窗口中都存在这，所以必然存在这重复计算的逻辑
  • 考虑使用单调队列，队列内只存在窗口内的元素，队列内元素递减，可以保证所有的数据只会入队和出队一次，减少时间复杂度

算法流程

• 初始化滑动窗口的left 和 right 从下标[1-k,0]的位置开始
• 如果left > 0 说明窗口已经在数组中了，并且单调队列的第一个元素和 nums[left-1]相等时候，说明该元素已经不在滑动窗口了，需要移除。
• 如果单调队列不为空且最后一个元素小于新加入的 nums[right] 元素，则需要维护单调队列为递减状态，所以将最后一个元素移除，直到其大于新加入元素
• 将新加入的 nums[right] 元素加入单调队列，因为上一步的操作，当前单调队列一定是递减的
• 如果 left >= 0，说明窗口在数组中，因为单调队列递减，所以第一个元素一定是当前滑动窗口最大值

var maxSlidingWindow = function(nums, k){
  if (nums.length === 0 || k === 0) {
    return []
  }
  let queue = []
  let res = []
  // 有一说一这个循环条件，我确实是写不出来
  for (let right = 0,left = 1-k; right < nums.length; left++,right++) {
    if (left > 0 && queue[0] === nums[left-1]) {
      queue.shift();
    }

    while(queue.length != 0 && queue[queue.length - 1] < nums[right]) {
      queue.pop();
    }
     queue.push(nums[right]);
    if(left >= 0) {
        res[left] = queue[0];
    }
  }
  return res;
}