239. 滑动窗口最大值

题目描述

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

1. 题型判断

本题要求每个长度为 k 的连续子数组中的最大值。

因为窗口长度固定，并且窗口会从左到右每次滑动一格，所以这是一个典型的固定长度滑动窗口问题。

普通滑动窗口只需要维护窗口边界，但这道题还要快速拿到窗口最大值。如果每次窗口移动后都重新遍历 k 个元素找最大值，时间复杂度会变成 O(n * k)，容易超时。

因此需要在滑动窗口基础上使用单调队列维护最大值。

2. 指针含义

使用闭区间窗口 [left, right]。

right：当前遍历到的元素下标，负责向右扩展窗口。
left：当前窗口左边界，固定长度窗口中可以由 right - k + 1 得到。
deque：单调递减队列，保存数组下标。
ans：保存每个窗口的最大值。

队列里存的是下标，而不是值。这样既能通过 nums[deque[0]] 得到当前最大值，也能判断队头元素是否已经离开窗口。

单调队列满足：

nums[deque[0]] >= nums[deque[1]] >= nums[deque[2]] ...

所以队头下标对应的元素，就是当前窗口内的最大值。

3. 窗口或区间维护规则

每次遍历到 right 时，需要做三件事。

第一，移除已经离开窗口的下标。

当队头下标 deque[0] <= right - k 时，说明它已经不在当前窗口 [right - k + 1, right] 中，需要从队头删除。

while (deque.length && deque[0] <= right - k) {
  deque.shift();
}

第二，维护队列单调递减。

如果当前元素 nums[right] 大于等于队尾元素 nums[deque[deque.length - 1]]，那么队尾元素不可能再成为后续窗口最大值：

当前元素更大，位置还更靠右。
只要队尾元素还在窗口里，当前元素也一定在窗口里。

所以可以不断弹出队尾。

while (deque.length && nums[deque[deque.length - 1]] <= nums[right]) {
  deque.pop();
}

第三，把当前下标加入队尾。

deque.push(right);

完成这三步后，队头就是当前窗口的最大值下标。

4. 答案更新时机

本题是固定长度窗口。

只有当窗口长度达到 k 时，才开始记录答案。

遍历到 right 时，如果 right >= k - 1，说明第一个完整窗口已经形成，此时可以把队头对应的值加入答案：

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

注意答案要在完成过期元素移除、单调队列维护、当前元素入队之后更新。这样 deque[0] 一定是当前窗口内的最大值。

5. 边界条件与易错点

边界条件：

如果 nums.length === 0，返回空数组。
如果 k === 1，每个窗口只有一个元素，结果就是原数组。
如果 k === nums.length，结果只有一个值，即整个数组最大值。

易错点：

单调队列建议存下标，不要只存值。因为窗口滑动时需要判断队头元素是否过期。
移除过期元素的条件是 deque[0] <= right - k，表示该下标已经在当前窗口左侧。
队列维护的是单调递减，不是普通栈；队头是最大值，队尾用于插入新元素。
固定窗口长度达到 k 后再更新答案，也就是 right >= k - 1。
如果使用 shift()，语义最直观；在 JavaScript 中极端数据下可能有移动成本，也可以用队头指针优化。

错误思路示例：

for (let i = 0; i < nums.length - k + 1; i++) {
  for (let j = i; j < i + k; j++) {
    // 每个窗口都重新找最大值
  }
}

这种写法每个窗口都重新扫描一遍，时间复杂度是 O(n * k)。虽然逻辑简单，但没有利用相邻窗口之间只有一个元素进、一个元素出的特点。

6. 代码实现

写法一：单调队列

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // deque 中保存的是数组下标，不是具体的值
  // 并且这些下标对应的值会保持从大到小排列
  const deque = [];
  const ans = [];

  for (let right = 0; right < nums.length; right++) {
    // 当前窗口是 [right - k + 1, right]
    // 如果队头下标 <= right - k，说明它已经滑出窗口，需要删除
    // 这里用 while，是为了保证队头所有过期下标都被清理干净
    // 虽然正常每轮最多过期一个队头，但 while 写法更稳，也符合队列清理模板
    while (deque.length && deque[0] <= right - k) {
      deque.shift();
    }

    // 维护单调递减队列
    // 如果队尾元素 <= 当前元素，那么队尾元素不可能再成为最大值
    // 因为当前元素更大，并且下标更靠右，生命周期更长
    // 这里必须用 while，因为当前元素可能连续淘汰多个比它小的队尾元素
    // 例如 deque 对应值是 [5, 3, 1]，当前值是 6，就要把 1、3、5 都弹出
    while (deque.length && nums[deque[deque.length - 1]] <= nums[right]) {
      deque.pop();
    }

    // 当前元素入队，等待成为当前或后续窗口的最大值候选
    deque.push(right);

    // right >= k - 1 表示已经形成了第一个长度为 k 的完整窗口
    // 队头下标对应的值就是当前窗口最大值
    if (right >= k - 1) {
      ans.push(nums[deque[0]]);
    }
  }

  return ans;
};

写法二：队头指针优化

Array.prototype.shift() 会移动数组元素。为了让每次队头删除也保持常数级操作，可以用 head 表示当前有效队头位置。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  // deque 保存下标，head 指向当前有效队头
  // 这样删除队头时只需要移动 head，不需要调用 shift()
  const deque = [];
  const ans = [];
  let head = 0;

  for (let right = 0; right < nums.length; right++) {
    // 当前窗口左边界是 right - k + 1
    // deque[head] <= right - k 表示队头已经不在窗口内
    // 这里用 while，是为了把所有已经失效的队头下标都跳过
    // 使用 head 指针时，旧下标不会真的从数组中删除，所以更需要连续跳过无效位置
    while (head < deque.length && deque[head] <= right - k) {
      head++;
    }

    // 从队尾开始删除所有小于等于 nums[right] 的元素
    // 删除后，deque 从 head 到末尾仍然对应一个单调递减序列
    // 这里必须用 while，因为新元素可能比队尾多个元素都大
    // 只有把这些元素全部弹出，队头才始终能代表当前窗口最大值
    while (
      head < deque.length &&
      nums[deque[deque.length - 1]] <= nums[right]
    ) {
      deque.pop();
    }

    // 把当前下标加入队尾
    deque.push(right);

    // 窗口长度达到 k 后，队头就是当前窗口最大值的下标
    if (right >= k - 1) {
      ans.push(nums[deque[head]]);
    }
  }

  return ans;
};

7. 复杂度分析

写法一：

时间复杂度：理论上每个下标最多入队一次、出队一次，单调队列逻辑是 O(n)；但 JavaScript 的 shift() 可能触发元素移动，极端情况下会带来额外开销。
空间复杂度：O(k)，队列中最多保存当前窗口相关的下标。

写法二：

时间复杂度：O(n)，每个下标最多入队一次、出队一次。
空间复杂度：O(k)，队列最多保存窗口内可能成为最大值的下标。

ON THIS PAGE

#239. 滑动窗口最大值

#题目描述

#1. 题型判断

#2. 指针含义

#3. 窗口或区间维护规则

#4. 答案更新时机

#5. 边界条件与易错点

#6. 代码实现

#写法一：单调队列

#写法二：队头指针优化

#7. 复杂度分析