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

场景引入

给你一个数组和窗口大小 k，窗口从左到右滑动，每次返回窗口内的最大值。

数组: [1, 3, -1, -3, 5, 3, 6, 7], k = 3

窗口位置                最大值
[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

暴力做法是每次在窗口内找最大值，时间 O(nk)。用单调队列可以做到 O(n)。

核心思路

为什么需要单调队列

普通队列只能在一端进另一端出，无法高效获取最大值。我们需要一种特殊的队列，满足：

1. 队头始终是当前窗口的最大值
2. 新元素从队尾入队时，把前面所有比它小的元素都移除

这就是单调递减队列（从队头到队尾递减）。

核心逻辑

处理 [1, 3, -1, -3, 5, 3, 6, 7], k=3:

i=0: 入队1                       队列: [1]
i=1: 1<3, 弹出1, 入队3            队列: [3]
i=2: -1<3, 直接入队               队列: [3, -1]    窗口满, max=3
i=3: -3<-1, 直接入队              队列: [3, -1, -3] max=3
i=4: 弹出-3,-1(都<5), 入队5       队列: [5]        max=5
     (3已过期，但已被弹出)
i=5: 3<5, 直接入队                队列: [5, 3]     max=5
i=6: 弹出3(<=6), 入队6            队列: [5, 6]     哦不对...

等等，这里有问题。让我重新解释：队列里存的是索引而非值，这样才能判断队头元素是否已经滑出窗口。

i=0: 入队0                       队列索引: [0]     值: [1]
i=1: nums[0]<nums[1], 弹出0, 入队1 队列索引: [1]     值: [3]
i=2: nums[2]<nums[1], 入队2        队列索引: [1,2]   值: [3,-1]   max=3
i=3: nums[3]<nums[2], 入队3        队列索引: [1,2,3] 值: [3,-1,-3] max=3
i=4: 弹出3,2,1(值都<=5), 入队4     队列索引: [4]     值: [5]      max=5
i=5: nums[5]<nums[4], 入队5        队列索引: [4,5]   值: [5,3]    max=5
i=6: 弹出5(3<=6), 入队6            队列索引: [4,6]   值: [5,6]    max=6
     检查队头: 4 <= 6-3=3? 不是     （但实际上 i-k=3, 4>3 没过期）
     等等，4 <= 6-3=3? 不，4>3所以没过期。
     但这里 5<6 所以应该弹出... 让我重算：
i=6: nums[5]=3<=nums[6]=6, 弹出5; nums[4]=5<=6, 弹出4; 入队6
     队列索引: [6]    值: [6]      max=6
i=7: nums[6]=6<=7, 弹出6, 入队7   队列索引: [7]     值: [7]      max=7

可视化演示

LC 239. 滑动窗口最大值

加载可视化中...

代码实现

LC 239. 滑动窗口最大值

function maxSlidingWindow(nums, k) {
  let deque = []; // 存索引，维护单调递减
  let result = [];

  for (let i = 0; i < nums.length; i++) {
    // 1. 维护单调性：弹出所有比当前值小的
    while (deque.length > 0 && nums[deque[deque.length - 1]] <= nums[i]) {
      deque.pop();
    }

    // 2. 当前索引入队
    deque.push(i);

    // 3. 队头过期检查：滑出窗口的元素移除
    if (deque[0] <= i - k) {
      deque.shift();
    }

    // 4. 窗口形成后记录结果
    if (i >= k - 1) {
      result.push(nums[deque[0]]); // 队头就是最大值
    }
  }

  return result;
}

逐步分解

代码中每一步的作用：

第 1 步：维护单调递减

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

新元素入队前，把队尾所有比它小的都弹出。因为这些小元素在窗口中永远不会成为最大值——它们在新元素还在窗口中的时候就已经不可能是答案了。

第 2 步：入队

当前索引入队。存索引而非值，是为了第 3 步判断是否过期。

第 3 步：过期检查

if (deque[0] <= i - k) {
  deque.shift();
}

如果队头的索引已经不在窗口范围内（<= i - k），就从队头移除。

第 4 步：记录结果

当 i >= k - 1 时，窗口已经形成，队头就是当前窗口的最大值。

单调队列 vs 单调栈

	单调栈	单调队列
数据结构	栈（一端操作）	双端队列（两端操作）
解决问题	下一个更大/更小元素	滑动窗口最值
维护方式	入栈前弹出违反单调性的	入队前从队尾弹出 + 队头过期移除
队头/栈底	不关心	队头是答案

单调队列比单调栈多了一个操作：从队头移除过期元素。这正是"滑动窗口"的特性——窗口有大小限制。

为什么用数组模拟双端队列

JavaScript 没有原生 deque。这里用数组 + push/pop/shift 模拟。shift() 是 O(n) 的，严格来说不够高效。面试中可以和面试官说明这一点，然后补充：

• 可以用链表实现真正的 O(1) 双端队列
• 实际竞赛中用数组 + 头指针偏移模拟

复杂度分析

	时间复杂度	空间复杂度
暴力法	O(nk)	O(1)
单调队列	O(n)	O(k)

每个元素最多入队一次、出队一次，所以总操作是 O(n)。队列最多存 k 个元素，空间 O(k)。

LeetCode 练习

1. LC 239. 滑动窗口最大值（困难）
2. LC 862. 和至少为 K 的最短子数组（困难，单调队列变种）
3. LC 1438. 绝对差不超过限制的最长连续子数组（中等，两个单调队列）