59.滑动窗口的最大值.md

题目

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 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

思路

用一个双端队列window来存储滑动窗口

队列中存储滑动窗口的索引，根据窗口末尾元素和首位元素判断首位元素是否应该被移出队列

当前进入的元素下标 - 窗口头部元素的下标 >= k 头部元素移出队列

当新元素进入队列时，从队列末尾元素开始比较，将比新元素小的元素全部移出队列，这样可以保证队列中首个元素永远是窗口最大值

第k次遍历后开始向结果中添加最大值（滑动窗口首位元素）

时间复杂度O(n)

空间复杂度O(n)

代码

    function maxInWindows(num, size) {
      const window = [];
      const result = [];
      if (Array.isArray(num) && num.length > 0 && size > 0) {
        for (let i = 0; i < num.length; i++) {
          if (i - window[0] >= size) {
            window.shift();
          }
          let n = window.length - 1;
          while (n >= 0 && num[window[n]] < num[i]) {
            n--;
            window.pop();
          }
          window.push(i);
          if (i >= size - 1) {
            result.push(num[window[0]]);
          }
        }
      }
      return result;
    }