题目描述

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

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

进阶：

你能在线性时间复杂度内解决此题吗？

示例：

略。

提示：

略。

来源：LeetCode

思路

暴力搜索，思路最简单，时间复杂度 O(n*k)。但是进阶要求了线性时间复杂度，所以这个方法基本不用试了，试了估计也是超时。

维护一个 双端队列 ，记录元素下标，队头始终是窗口中最大的那个值。新加入元素时，

  1. 判断队头是否已经滑出了窗口，这个就是队列存储元素下标的原因。可以直接通过新元素与队头下标差来判断得出。若是，移除队头；
  2. 判断是否大于队头，是的话，前面全部移除，因为前面不会有比新元素大的了，我们只要窗口中的最大值；
  3. 判断新元素是否大于队尾，要从队尾开始，一个个把小于新元素的尾巴移除。这样的话，当队头移除的时候，新队头才是最大的。

解法

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
const maxSlidingWindow = function(nums, k) {
  const deque = [];
  const result = [];

  for (let i = 0; i < nums.length; i++) {
    // 队头已不在窗口内，移除
    if (i - deque[0] >= k) {
      deque.shift();
    }

    // 新加入元素大于队尾，要将队尾移除
    while (nums[i] > nums[deque[deque.length - 1]]) {
      deque.pop();
    }

    // 新加入元素大于队头，前面全部移除
    if (nums[i] > nums[deque[0]]) {
      while (deque.length) deque.shift();
    }

    deque.push(i);

    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
};
Last Updated:
Contributors: henri.zhang