题目

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路

暴力去找窗口中的最大值，复杂度较高。这里考虑将窗口中的最大值，设法保留下来

使用一个双端队列，存放所有可能为窗口最大值（实际存放下标），且最大值位于队首
从数组的首位开始扫描遍历，遍历到某数item的时候，存在以下三种情况：

1. 队列中的所有数字都比item小，那么队列中的所有数字不能在包括item的窗口中成为最大值，所以队列中的数字全部删除，item作为队首存入队列
2. 队列中的数字都比item大，item还是有可能作为后续窗口的最大值，存入队尾
3. 队列中的数字部分比item大，部分比item小，这种情况一定是前几个数比item大，后几个数比item小，比item小的后几个数不再可能是最大值，删除这些数，将item存入队尾
   注意：因为滑动窗口大小为size，所以当队首的数字下标与当前遍历的item下标距离达到size的时候，就应该将队首除去

PS：第三条规则其实包含了1、2条，所以规则合并。在队列前，比item大的都还有可能是最大值，所以对前几个比item大的数字不做操作。在队列后，比item小的数，不再可能成为最大值，所以这些数字全部pop掉，将item入队

代码

function maxInWindows (num, size) {
  // write code here
  if (!num || !size || size > num.length) return []
  let maxList = []
  let queue = []
  num.forEach((item, index) => {
    // 队列前已经滑出窗口的数，不再成为窗口最大值，删除
    if (index - queue[0] >= size) queue.shift()
    while (queue.length > 0) {
      // 队列前比当前小的数，都不能再是窗口中的最大值，删除
      if (num[queue[0]] < item) queue.shift()
      else break
    }
    // 队尾比当前小的数，不能成为窗口中的最大数，删除
    while (queue.length > 0) {
      if (num[queue[queue.length - 1]] < item) queue.pop()
      else break
    }
    // 将该数加入
    queue.push(index)
    // 此时队首一定是窗口最大值
    if (index >= size - 1) {
      maxList.push(num[queue[0]])
    }
  })
  return maxList
}