Vue.js

Appearance

On this page

单调队列原理与模板 ​

单调栈只能从一端操作，而单调队列可以从两端操作——这让它能够解决滑动窗口类型的问题。

什么是滑动窗口？想象一个固定大小的窗口在数组上滑动，每次你需要快速获取窗口内的最大值或最小值。暴力做法是 O(nk)，而单调队列可以做到 O(n)。

什么是单调队列 ​

单调队列是一种特殊的双端队列（Deque），它的特点是：

  1. 队列中的元素保持单调性（递增或递减）
  2. 可以从两端操作：队头出元素，队尾进元素
  3. 队头始终是当前窗口的最值

核心应用：滑动窗口最大值 ​

问题：给定数组 nums 和窗口大小 k，返回每个窗口的最大值。

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

暴力做法 ​

javascript
// 每个窗口遍历一次找最大值
// 时间复杂度：O(nk)

单调队列做法 ​

javascript
function maxSlidingWindow(nums, k) {
  const n = nums.length;
  const result = [];
  const deque = [];  // 存索引，对应值单调递减
  
  for (let i = 0; i < n; i++) {
    // 1. 移除超出窗口范围的元素（从队头）
    while (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }
    
    // 2. 维护单调性：移除比当前元素小的（从队尾）
    while (deque.length > 0 && nums[deque[deque.length - 1]] < nums[i]) {
      deque.pop();
    }
    
    // 3. 当前元素入队
    deque.push(i);
    
    // 4. 记录结果（窗口形成后）
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

执行过程可视化 ​

以 nums = [1,3,-1,-3,5,3,6,7], k = 3 为例：

i=0, num=1:
  deque = [0]
  窗口未形成，不记录

i=1, num=3:
  3 > 1，弹出队尾
  deque = [1]
  窗口未形成，不记录

i=2, num=-1:
  -1 < 3，直接入队
  deque = [1, 2]
  窗口 [1,3,-1]，最大值 = nums[1] = 3
  result = [3]

i=3, num=-3:
  -3 < -1，直接入队
  deque = [1, 2, 3]
  检查队头：1 >= 3-3+1=1，不过期
  窗口 [3,-1,-3]，最大值 = nums[1] = 3
  result = [3, 3]

i=4, num=5:
  5 > -3，弹出；5 > -1，弹出；5 > 3，弹出
  deque = [4]
  检查队头：1 < 4-3+1=2，过期但已弹出
  窗口 [-1,-3,5]，最大值 = nums[4] = 5
  result = [3, 3, 5]

i=5, num=3:
  3 < 5，直接入队
  deque = [4, 5]
  窗口 [-3,5,3]，最大值 = nums[4] = 5
  result = [3, 3, 5, 5]

i=6, num=6:
  6 > 3，弹出；6 > 5，弹出
  deque = [6]
  窗口 [5,3,6]，最大值 = nums[6] = 6
  result = [3, 3, 5, 5, 6]

i=7, num=7:
  7 > 6，弹出
  deque = [7]
  窗口 [3,6,7]，最大值 = nums[7] = 7
  result = [3, 3, 5, 5, 6, 7]

关键操作解析 ​

为什么从队尾弹出？ ​

维护单调递减的顺序。当新元素更大时，之前那些较小的元素永远不可能成为最大值了——因为新元素比它们大，而且会比它们更晚离开窗口。

为什么从队头弹出？ ​

移除超出窗口范围的元素。窗口左边界是 i - k + 1，索引小于此的元素已经"过期"。

为什么队头就是最大值？ ​

因为队列是单调递减的（队头最大），而且队头元素一定在窗口范围内（过期的已被移除）。

单调队列 vs 单调栈 ​

特性单调栈单调队列
操作端单端（栈顶）双端
典型问题下一个更大元素滑动窗口最值
窗口限制无有固定大小
获取最值不直接支持队头就是最值

滑动窗口最小值 ​

只需改变比较方向（维护单调递增队列）：

javascript
function minSlidingWindow(nums, k) {
  const n = nums.length;
  const result = [];
  const deque = [];  // 存索引，对应值单调递增
  
  for (let i = 0; i < n; i++) {
    while (deque.length > 0 && deque[0] < i - k + 1) {
      deque.shift();
    }
    
    // 改成 > 号，维护递增
    while (deque.length > 0 && nums[deque[deque.length - 1]] > nums[i]) {
      deque.pop();
    }
    
    deque.push(i);
    
    if (i >= k - 1) {
      result.push(nums[deque[0]]);
    }
  }
  
  return result;
}

复杂度分析 ​

  • 时间复杂度：O(n)。每个元素最多入队一次、出队一次。
  • 空间复杂度：O(k)。队列最多存储 k 个元素。

技巧总结 ​

单调队列解决滑动窗口问题的模板：

  1. 队尾维护单调性：移除比当前元素"差"的候选
  2. 队头移除过期元素：超出窗口范围的要移除
  3. 队头就是答案：因为队列保持单调，队头是最值
  4. 存储索引：方便判断是否过期

单调队列是滑动窗口类问题的利器，掌握后可以高效解决很多区间最值问题。

在 GitHub 上编辑此页