239.滑动窗口最大值

题目类别	难度
堆/滑动窗口	easy

题目

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

解法

1. 暴力法

移动滑动窗口，比较最大值。时间复杂度O((N-k*k)(N数组长度)这样会超出时间复杂度

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

2. 优化：双端队列

TIP

解题思路： 使用一个双端队列存储窗口中值的 索引 ，并且保证双端队列中第一个元素永远是最大值，那么只需要遍历一次 nums，就可以取到每次移动时的最大值。

• 比较当前元素 i 和双端队列第一个元素（索引值），相差>= k时队首出列
• 依次比较双端队列的队尾与当前元素i对应的值，队尾元素值较小时出列，直至不小于当前元素i的值时，或者队列为空，这是为了保证当队头出队时，新的队头依旧是最大值
• 当前元素入队
• 从第 K 次遍历开始，依次把最大值（双端队列的队头）添加到结果 result 中
• 时间复杂度：O(n)

function maxInWindows(num, size) {
  // 双端队列（两端都可以实现插入和删除）
  // 队列首位永远是最大值
  // 每次进来一个数，依次和前面的数比较，如果进来的数大，则前面的数直接弹出（在后面不可能最大）
  // 如果进来的数小，则比较下标，下标不存在的将其删除

  // 数组实现双端队列，arr存的是下标，arr[0]存最大值下标
  var arr = [];
  // 结果数组
  var res = [];

  if (size === 0) {
    return res;
  }

  for (var i = 0; i < num.length; i++) {
    // 从第一个开始循环（可以理解成滑动窗口右侧从第一个移动到最后一个）
    // 进来一个数，依次从最后一个数开始比较
    while (arr.length > 0 && num[i] > num[arr[arr.length-1]]) {
      // 如果进来的数比最后一个大，则将最后一个踢出去，pop
      arr.pop();
    }
    arr.push(i);

    // 再判断前面的数是否超了，由于每次进来的数如果更大，则将前面的踢出去，导致arr[0]的下标永远在最前面
    if (i - arr[0] + 1 > size) {
      arr.shift();
    }
    if (i >= size - 1) {
      res.push(num[arr[0]]);
    }
  }
  return res;
}