题解 | #滑动窗口的最大值#

function maxInWindows(num, size)
{
  // write code here
 if (size === 0) {
    return []
}
if (size === 1) {
    return num
}
let queue = [0]
let max = []
for (let i = 1; i < num.length; i++) {
    //queue中存储的是下标，当指针与最大值下标超过size,自动出队
    if ((i - queue[0]) >= size) {
        queue.shift()
    }
    //指针到的值大于队里最大值，清空，指针最大值入队
    if (num[i] > num[queue[0]]) {
        queue = []
        queue.push(i)
    } else {
        //指针的值小于队里最大值，当大于队尾，则队尾出队（队尾是队内最小值，唯一机会是等前面的随窗口滑动被移出队列而成为最大值上位）
        while (queue.length > 0 && num[i] > num[queue[queue.length-1]]) {
            queue.pop()
        }
        //指针到的值小于队里最大值，且小于等于队尾，加入队尾行列，等机会上位
        queue.push(i)
    }
    //根据窗口大小，当指针下标大于等于size-1时，才开始最大值输入，指针每移动一次，一个最大值
    if (i >= size - 1) {
        max.push(num[queue[0]])
    }
}
return max
}

思路:max存储最大值;queue(两端开口的队列)存储滑动窗口最大值和随窗口滑动等待上位的可能的最大值[注:存储的都是下标]。queue:[滑动窗口最大值下标，等待上位的若干个可能成为最大值的下标]，queue[0]默认就是最大值的下标。

情况1：滑动窗口大小为0,return null;

情况2：滑动窗口大小为1,return num;

情况3：滑动窗口的大小>=2,仔细分类，随i指针滑动，queue中存储的是下标，当指针i与最大值下标queue[0]超过滑动窗口大小size,最大值queue[0]出队，然后指针i滑动到i >= size - 1，开始有滑动窗口，max开始赋值，最复杂的情况就是窗口滑动过程中，对于最大值，和可能成为最大值的数的下标的存储与否。a.当指针i的值大于队里最大值queue[0]，指针i成为滑动窗口可能的最大值，那后面等待上位的可能最大值也没机会上位了，就清空queue，i入队成为最大值queue[0];b.当指针i的值小于等于队里最大值queue[0]，由于不知道随窗口滑动后面的值，该i有机会上位的，需要加入队尾，不过需要跟原队尾比较（队尾是队内最小值，唯一机会是等前面的随窗口滑动被移出队列而成为最大值上位），比原队尾大，就原队尾没机会上位移出去。