LeetCode 239. 滑动窗口最大值

Skyme2026/9/17大约 5 分钟

LeetCode 239. 滑动窗口最大值

题目核心

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

解题思考过程

第一步：暴力解法

每个窗口扫描 k 个元素找最大值：

时间复杂度：O(nk)
空间复杂度：O(1)（不计输出）

n 和 k 都到 10⁵ 级别时必然超时。

第二步：堆行不行？

维护一个大顶堆，元素带着下标入堆；堆顶如果已经滑出窗口就懒删除（弹出）：

时间复杂度：O(n log n)
空间复杂度：O(n)

能过，但这题有更贴合"窗口"结构的 O(n) 做法。

第三步：想到单调队列

窗口每移动一步，发生两件事：

右侧新元素 nums[r] 进来。
左侧旧元素 nums[r-k] 离开。

我们希望队首永远是当前窗口最大值。关键观察：

新元素 nums[r] 入队时，所有比它小的队中元素，在它存活的窗口里永远没有出头之日——它更晚离开、值还更大，所以可以直接把这些小元素从队尾弹出。

于是队列里的下标对应的值单调递减，这就是单调队列（双端队列 Deque）。

每个右指针位置按顺序做四件事：

① 队首下标如果已经滑出窗口（< r-k+1）→ 从队首弹出
② 队尾元素如果 ≤ nums[r] → 从队尾弹出（维护单调递减）
③ 把 r 入队
④ 窗口形成（r ≥ k-1）→ 队首对应的值就是当前窗口最大值

第四步：为什么是 O(n)？

每个下标最多入队一次、出队一次（不管从队首还是队尾），所有操作加起来是线性的。

当前解法：单调队列（head 指针版）

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function (nums, k) {
  let queen = [];
  let ans = [];
  let head = 0;

  for (let r = 0; r < nums.length; r++) {
    // ① 队首滑出窗口 → head 后移
    while (head < queen.length && queen[head] < r - k + 1) {
      head++;
    }

    // ② 队尾比当前元素小 → 弹出
    while (head < queen.length && nums[r] > nums[queen[queen.length - 1]]) {
      queen.pop();
    }

    // ③ 当前下标入队
    queen.push(r);

    // ④ 窗口形成，记录队首最大值
    if (r >= k - 1) {
      ans.push(nums[queen[head]]);
    }
  }

  return ans;
};

代码逐行解释

为什么用 `head` 指针而不是 `shift()`？

let queen = [];
let head = 0;

JS 数组的 shift() 会移动整个数组的元素，频繁调用有开销。这里用 head 标记逻辑队首：

head 之前的元素逻辑上已出队，但物理上还留在数组里。
逻辑队列 = queen[head .. queen.length-1]。
判空条件是 head === queen.length，不是 queen.length === 0。

① 队首出窗

while (head < queen.length && queen[head] < r - k + 1) {
  head++;
}

当前窗口左边界是 r - k + 1，队首下标比它小说明已经不在窗口里，head++ 出队。

注意队列里存的是下标不是值——只有存下标，才能判断"是否滑出窗口"。

② 维护单调递减

while (head < queen.length && nums[r] > nums[queen[queen.length - 1]]) {
  queen.pop();
}

队尾对应的值比当前值小，就弹出队尾。循环结束后：

队列为空，或
队尾值严格大于 nums[r]。

这里用 > 而不是 >=：相等的元素保留在队列中，先入的那个出窗后，后入的还能顶上，行为最直观。（用 >= 提前弹出相等元素也正确，队列会短一点。）

一个容易看晕的细节：pop 会不会把 `head` 位置的元素删掉？

会，但恰好安全。假设逻辑队列只剩一个元素（head === queen.length - 1），当前值比它还大：

pop() 之后 queen.length === head → 逻辑空队
push(r) 时新元素正好落在下标 head 处
→ queen[head] 立刻又是新的最大值

所以 push 之后 queen[head] 永远是当前窗口最大值下标。

③④ 入队与记录

queen.push(r);

if (r >= k - 1) {
  ans.push(nums[queen[head]]);
}

前 k-1 个位置窗口还没形成；从 r = k-1 开始每个位置产出一个答案。

执行过程示例

以 nums = [1,3,-1,-3,5,3,6,7]、k = 3 为例（只看逻辑队列）：

r=0: 入队 [0]，窗口未形成
r=1: nums[1]=3 > nums[0]=1，弹出 0；入队 [1]
r=2: 入队 [1,2]；窗口最大值 nums[1]=3        ans=[3]
r=3: 下标 1 仍在窗内；入队 [1,2,3]；最大值 3  ans=[3,3]
r=4: 下标 1<2 出队；-1、-3 都比 5 小，依次弹出；入队 [4]；最大值 5  ans=[3,3,5]
r=5: 3<5 保留；入队 [4,5]；最大值 5           ans=[3,3,5,5]
r=6: 队尾 3、5 都比 6 小，弹出；入队 [6]；最大值 6  ans=[3,3,5,5,6]
r=7: 7>6 弹出 6；入队 [7]；最大值 7           ans=[3,3,5,5,6,7]

复杂度分析

时间复杂度：O(n) — 每个下标至出入队各一次
空间复杂度：O(k)（逻辑队列长度不超过窗口大小）；
            head 指针版物理数组最多 O(n)

替代写法：标准 Deque（shift/pop）

如果不在意 shift 的常数开销，逻辑更直白：

var maxSlidingWindow = function (nums, k) {
  const deque = []; // 存下标，对应值单调递减
  const ans = [];

  for (let r = 0; r < nums.length; r++) {
    // 队首出窗
    if (deque.length && deque[0] < r - k + 1) {
      deque.shift();
    }

    // 队尾更小则弹出
    while (deque.length && nums[r] >= nums[deque[deque.length - 1]]) {
      deque.pop();
    }

    deque.push(r);

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

  return ans;
};

和 head 指针版只是"谁来充当逻辑队首"的区别。

易错点

队列存下标，不要存值：否则无法判断队首是否已经滑出窗口。
出窗判断的边界：queen[head] < r - k + 1，左边界是随 r 变化的，不要写成固定的 r - k（会晚一个位置出队，不过单调队列里通常不影响最大值，但语义错了）。
两个 while 的条件都要带 head < queen.length：head 指针版里数组物理长度不代表逻辑长度，写成 0 < queen.length 会读到已出队元素。
先处理出窗、再处理入队：顺序反过来在多数情况下也能跑，但窗口左边界的语义会混，按固定顺序写最稳。