算法面试：如何用单调队列求滑动窗口最大值？

题干与适用场景

给定整数数组 nums 和窗口大小 k。窗口先覆盖下标 0 到 k - 1，随后每次向右移动一格；返回每个 窗口的最大值。约束为 1 <= nums.length <= 100000、1 <= k <= nums.length。例如：

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
结果 = [3, 3, 5, 5, 6, 7]

目标时间复杂度为 O(n)，输出数组之外的额外空间为 O(k)。标准题目保证数组非空且 k 有效；如果生产 接口需要接受空数组或非法 k，应先单独定义返回值或异常，不能把未约定行为混进算法证明。

2026 年多份中英文算法面试材料仍把 Sliding Window Maximum 列为单调双端队列的直接练习，并要求解释队首、 过期下标、队尾淘汰与摊还复杂度。中文公开题解也在 2026 年继续比较暴力与双端队列方案。本题属于通用算法 与数据结构能力，准确分类为 coding，不因示例使用 TypeScript 而归入前端。

面试官考察点

第一，能否识别“窗口每次只进一个、出一个，却要持续求极值”的结构。暴力法把相邻窗口中重复的 k - 1 个元素重新扫描；单调队列只保留仍可能成为当前或未来最大值的候选下标。

第二，是否能解释为什么存下标而不是只存值。窗口过期由位置决定；相同数值可能来自不同位置。没有下标， 无法可靠判断队首的最大值是否已经离开窗口。

第三，能否证明队尾元素可以永久删除。若较旧元素 nums[j] 不大于新元素 nums[i] 且 j < i，新元素更大 或相等，又更晚离开窗口；只要两者同时存在，旧元素就不可能获胜。这是支配关系，不是为了让队列“看起来有序”。

最后，复杂度是否使用摊还分析。某一轮可能连续弹出多个下标，单轮不是严格 O(1)；但每个下标只入队一次， 也最多从队首或队尾离队一次，所以全部双端队列操作为 O(n)。

回答前需要澄清的问题

• 窗口长度固定吗？ 本题固定为 k；可变窗口需要重新定义过期条件和查询接口。
• 数组是否可能为空？ 标准约束排除空数组；若扩展接口允许空输入，应明确返回空数组还是拒绝。
• k 是否保证有效？ 本题保证有效；示范实现仍做运行时校验，防止负长度结果或越界访问。
• 元素能否重复或为负数？ 可以。算法只依赖比较与下标，不依赖正数或互异性。
• 相同值应保留新下标还是旧下标？ 两者都能得到正确最大值；本文删除旧的相等值，保留更晚过期的新下标。
• 空间是否真的要求 O(k)？ 是。只移动数组头指针却不回收旧槽位的 JavaScript 实现可能实际保留 O(n) 存储；本文使用容量为 k 的环形缓冲区。
• 只返回最大值还是还要最大值下标？ 主问题返回值；若需要下标，直接输出队首下标，并另行定义重复最大值的选择规则。
• 是否允许修改输入数组？ 不允许；实现只读取 nums。

30 秒回答框架

“我会用双端队列保存候选下标，并维持下标从队首到队尾递增、对应值严格递减。处理下标 i 时，先从队首 删除不在当前窗口内的下标；再从队尾删除值小于等于 nums[i] 的下标，因为新元素至少一样大且会更晚过期， 旧元素不可能再成为最大值。然后把 i 入队。首个完整窗口形成后，队首对应值就是答案。每个下标入队一次、 最多离队一次，因此总时间 O(n)；队列最多保存 k 个下标，额外空间 O(k)。”

分步骤深入解答

第一步：用基础方案定位重复工作。

当 n 和 k 都接近 100000 时，暴力法可能进行约 10^10 次比较。堆是容易解释的过渡方案，但它维护所有 元素间的优先级；题目每次只读取最大值，保留被更新元素支配的旧候选没有价值。

第二步：把“无用元素”写成支配规则。

假设 j < i 且 nums[j] <= nums[i]。在任何同时包含 j 和 i 的未来窗口中，j 的值不会超过 i； 当窗口继续右移时，j 还会先于 i 过期。因此从 i 到达的时刻起，j 永远不可能再次成为窗口最大值， 可以从候选集合永久删除。

删除条件使用小于等于，意味着相等值只保留最新下标，队列值严格递减。若只删除更小值，也仍然正确，但队列 值只是非递增并会保留多个相等候选。两种策略不能在证明和代码里混用。

第三步：维护四个可检查的不变量。

处理完下标 i 后：

1. 队列中的下标严格递增，顺序与到达顺序一致。
2. 队列中的下标都在当前范围 [i - k + 1, i] 内。
3. 从队首到队尾，对应数组值严格递减。
4. 当前窗口中每个被删除的下标，都有一个更晚且不小于它的候选留在支配链上。

前三条说明队首是保留候选中的最大值；第四条说明被删除元素不会让真实最大值消失。两部分合在一起，队首才 能代表整个窗口，而不只是队列内部的最大值。

第四步：实现实际占用 O(k) 的环形双端队列。

export function maxSlidingWindow(
  nums: readonly number[],
  k: number,
): number[] {
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    throw new RangeError("k must be an integer between 1 and nums.length");
  }

  const deque = new Int32Array(k);
  let head = 0;
  let size = 0;
  const result: number[] = [];

  for (let i = 0; i < nums.length; i += 1) {
    while (size > 0 && deque[head] <= i - k) {
      head = (head + 1) % k;
      size -= 1;
    }

    while (size > 0) {
      const back = (head + size - 1) % k;
      if (nums[deque[back]] > nums[i]) break;
      size -= 1;
    }

    deque[(head + size) % k] = i;
    size += 1;

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

  return result;
}

环形缓冲区容量恰好为 k。每轮入队前，过期元素已经删除，因此当前窗口最多已有 k - 1 个有效下标， 写入不会覆盖队首。Int32Array 足以保存最多 100000 的下标；如果题目允许超过 32 位范围的索引，应改用普通 数值数组或重新约束输入。

第五步：证明算法返回每个窗口的真实最大值。

初始化时队列为空，不变量成立。处理新下标时，队首删除只移除窗口之外的元素，所以不影响当前答案。队尾删除 依据支配规则：每个被删元素都有更新且不小于它的 i 替代。把 i 加到队尾后，下标继续递增，值继续严格 递减。

第一个完整窗口在 i = k - 1 形成。此后每轮队首都在窗口内；队列值严格递减使队首大于其余候选，而支配链 保证任何未保留元素都不可能大于某个保留元素。因此 nums[deque[head]] 等于当前窗口最大值。对所有 i 归纳，输出的 n - k + 1 个值都正确。

第六步：走查重复值和过期边界。

对示例，括号中记录“下标:值”：

i=0  [0:1]                  未形成窗口
i=1  [1:3]                  3 支配 1
i=2  [1:3, 2:-1]            输出 3
i=3  [1:3, 2:-1, 3:-3]      输出 3
i=4  [4:5]                  1 过期，5 支配 -1 和 -3，输出 5
i=5  [4:5, 5:3]             输出 5
i=6  [6:6]                  6 支配 5 和 3，输出 6
i=7  [7:7]                  7 支配 6，输出 7

数组 [4, 4, 4]、k = 2 时，第二个 4 会删除第一个 4，第三个再删除第二个；队列始终只有最新下标，两个 窗口仍都输出 4。这个例子能检查相等值条件，也能发现只存值时无法判断过期的问题。

第七步：准确给出摊还复杂度。

循环有两个 while，不能据此相乘成 O(nk)。每个下标只入队一次；离队后不会回来，因此所有队首弹出和 队尾弹出的总次数不超过 n。总时间为 O(n)。环形队列最多存 k 个下标，额外空间为 O(k)；结果数组有 n - k + 1 个元素，通常不计入额外空间。

第八步：用朴素 oracle 做差分验证。

固定用例覆盖：k = 1、k = n、全相等、严格递增、严格递减、全负数和标准混合示例。空数组与 k = 0 属于非法输入，预期抛出 RangeError。再生成短随机数组与随机有效 k，把结果和“逐窗口扫描最大值”的 朴素实现逐项比较；随机测试同时检查结果长度与每个窗口的队首值。

当 n 很小或只计算一个窗口时，暴力扫描更短、更易审查；当语言已经提供可靠双端队列时，应优先复用标准 容器。本文写环形缓冲区是为了让 TypeScript 示例的实际内存界限与 O(k) 分析一致。

高质量示范回答

“暴力法会为每个窗口扫描 k 个元素，最坏是 O(nk)。我会维护一个保存下标的单调双端队列。队列下标按 到达顺序递增，对应值从队首到队尾严格递减。

处理下标 i 时，先删除队首所有不大于 i - k 的过期下标。然后从队尾删除值小于等于 nums[i] 的下标： 新元素至少一样大，而且更晚离开窗口，所以旧元素不可能再成为最大值。接着把 i 放到队尾；当 i >= k - 1 时，队首就是当前窗口最大值。

正确性依赖两点：被队首删除的元素已经不在窗口内；被队尾删除的元素都有一个更新、不小于它且存活更久的 元素替代。队列保持值递减，所以剩余候选的最大值在队首。每个下标入队一次、最多离队一次，总操作数是 线性的，因此时间 O(n)；队列最多保存 k 个下标，额外空间 O(k)。我会重点测试 k = 1、k = n、 重复值、单调数组和负数，并用暴力实现做随机差分。”

常见错误

• 队列只存数值 → 相同值无法判断哪一个过期 → 保存下标，通过数组读取值。
• 只维护递减值，不删除过期队首 → 已离开窗口的旧最大值会继续被输出 → 每轮先按 i - k 清理队首。
• 把过期条件写成小于 i - k → 下标恰为 i - k 的元素已在窗口左侧之外 → 使用小于等于。
• 看到内层 while 就声称 O(nk) → 同一下标不会被反复弹出 → 用每个下标至多入队、离队一次做摊还分析。
• 使用 shift() 并宣称操作常数时间 → JavaScript 数组头删可能移动元素 → 使用标准 deque、头指针或环形缓冲区。
• 头指针只增不回收却声称空间 O(k) → 旧槽位仍可能让底层数组增长到 O(n) → 使用容量固定为 k 的环形存储。
• 相等值的弹出规则与证明不一致 → “严格递减”和“非递增”被混用 → 明确本文用小于等于删除旧值。
• 堆里只保存值 → 延迟删除仍无法识别过期元素 → 堆方案也必须保存下标。
• 只跑标准示例 → k = 1、重复值和递减数组中的边界错误未暴露 → 加入固定边界和随机 oracle。

追问及应对

追问一：为什么相等时删除旧下标仍然安全？

新下标的值相等，且一定比旧下标晚过期。在两者共存的所有窗口中，留下任意一个都能提供相同最大值；旧下标 先离开，不会在新下标过期后重新获得机会。因此保留新下标即可，还能缩短队列。

追问二：如果还要返回每个最大值第一次出现的下标呢？

相等值不能再删除旧下标；队尾只删除严格更小的值，使队列值非递增。这样队首保留当前窗口中最早的最大值。 若要求最后一次出现，则沿用本文删除小于等于的规则。返回规则改变了相等值策略，但没有改变 O(n) 界限。

追问三：为什么不用最大堆？

堆可以更快写出，使用值与下标并延迟删除后能得到正确答案；普通二叉堆中的过期元素若不在堆顶，会继续占用 空间，最坏可增长到 O(n)，时间为 O(n log n)。支持任意删除的索引堆可控制为 O(n log k) 和 O(k)， 但实现更复杂。若面试只要求先给可用方案，堆可以作为过渡，再优化为单调队列。

追问四：窗口同时需要最大值和最小值怎么办？

维护两个独立双端队列：一个对应值递减，队首给最大值；另一个对应值递增，队首给最小值。每个下标在每个 队列中仍然只入队和离队一次，所以总时间仍为 O(n)，额外空间为 O(k)。

追问五：如果每次窗口大小都会变化呢？

若左右边界仍单调向右移动，可以用当前左边界清理过期下标，单调队列仍适用；若窗口会向左扩张，先前永久 删除的候选可能重新进入范围，当前结构无法恢复它们。此时应改用平衡树、线段树或离线 RMQ，并根据更新与 查询模式选择复杂度。

追问六：数据是无限流，如何在线输出？

为每个到达元素分配递增序号，执行同样的过期和队尾删除；从第 k 个元素开始，每到一个元素立即输出一次 队首值。只保留最多 k 个候选下标和值，内存与流总长度无关。若上游会乱序到达，还需先定义事件时间窗口、 水位和迟到策略，这已经不是本题的顺序数组模型。

追问七：如何把方法推广到受限动态规划？

若转移形如“当前位置状态等于自身代价加上前 k 个状态的最大值”，可以让队列按 DP 值递减，队首提供转移 所需最大值，过期条件仍由下标决定。区别是比较对象从 nums[i] 变成 dp[i]；证明仍依赖更晚且不小的状态 支配旧状态。