单调队列：滑动窗口最大值

题面：给定数组 nums 和窗口大小 k，返回每个长度为 k 的连续窗口的最大值。例如 nums = [1,3,-1,-3,5,3,6,7]、k = 3 时结果是 [3,3,5,5,6,7]。

一、核心不变量

队列保存的是下标而不是值，并同时满足：

下标从队头到队尾递增；
对应值从队头到队尾单调递减，所以队头永远是当前窗口最大值；
队列中的每个下标都在窗口 [right - k + 1, right] 内。

处理新下标 right 时，先从队尾移除值小于等于 nums[right] 的下标。它们以后不可能成为最大值：新值更大且更晚过期。然后移除已经滑出窗口的队头，最后读取队头。

二、可运行实现

function maxSlidingWindow(nums, k) {
  if (!Array.isArray(nums)) throw new TypeError('nums must be an array')
  if (!Number.isInteger(k) || k < 1 || k > nums.length) {
    return []
  }

  const deque = []
  let head = 0
  const result = []

  for (let right = 0; right < nums.length; right += 1) {
    // 保持值从队头到队尾递减。
    while (
      head < deque.length &&
      nums[deque[deque.length - 1]] <= nums[right]
    ) {
      deque.pop()
    }
    deque.push(right)

    const firstValid = right - k + 1
    while (head < deque.length && deque[head] < firstValid) {
      head += 1
    }

    if (right >= k - 1) result.push(nums[deque[head]])

    // 头部长期前移后偶尔压缩数组，避免 shift() 的线性搬移。
    if (head > 64 && head * 2 > deque.length) {
      deque.splice(0, head)
      head = 0
    }
  }

  return result
}

每个下标最多入队一次、从队尾弹出一次、从队头过期一次，因此时间复杂度为 O(n)。队列长度最多 k，额外空间 O(k)；结果数组 O(n - k + 1) 属于输出空间。用 deque.shift() 直接出队会搬移剩余元素，在某些实现中使复杂度退化，使用头指针或真正的双端队列更稳妥。

三、为什么相等值也可以弹出

当 nums[old] === nums[new] 时，new 的下标更晚过期，保留它即可；从队尾弹出旧下标不会改变窗口最大值。若需要返回“最早出现的最大值下标”，则应使用严格小于 < 而不是 <=，并在题面中说明 tie-break 规则。

四、与堆和暴力法的取舍

方法	时间	额外空间	适用情况
每窗扫描	`O(nk)`	`O(1)`	小规模、先写基准实现
大顶堆	`O(n log k)`	`O(k)`	需要支持更复杂优先级或删除策略
单调队列	`O(n)`	`O(k)`	固定窗口 min/max，要求线性扫描

单调队列只适用于窗口边界按顺序滑动、并且旧元素一旦过期就不再回来的场景；如果窗口任意增删或需要查询中位数，应换用堆、平衡树或其他结构。

五、边界与追问

Q: `k = 1` 和 `k = nums.length` 如何处理？

A: k = 1 每个元素自己构成窗口，队列逻辑仍成立；k = nums.length 只输出一次全数组最大值。空数组或非法 k 按本实现返回 []，若题目要求抛错应先改契约。

Q: 为什么队列里存下标？

A: 只有下标能判断元素是否滑出窗口；只存值无法区分两个相等值的生命周期，也无法在左边界移动时删除正确元素。

Q: 能否用 `Math.max(...window)`？

A: 可以作为小样本基准，但每次展开窗口会产生 O(k) 扫描和参数数量限制，不能把它当作线性解法。

Q: 如何求滑动窗口最小值？

A: 把队列维护方向反过来，队头保持最小值；过期判断和复杂度不变。

来源：前端高频算法原题解析.pdf 的“滑动窗口最大值”；与滑动窗口、单调队列既有专题融合整理。

相关专题：滑动窗口基础知识速览、字符覆盖窗口、堆与优先队列。