困难C++8 分钟2,732 字

单调队列——排队买冰淇淋的有序队伍

你有没有在学校小卖部门口排过队?如果有个规矩:新来的人如果比前面的人都高,前面的人就会自动离开,直到把最高的留在队首,那么这条队伍就永远保持着“从队首到队尾,身高越来越矮”的顺序。这种特殊的队伍,在编程里就叫单调队列​​。

单调队列是一种内部元素始终保持单调递增或单调递减​的队列。它只能从队尾加入新元素,从队首或队尾删除旧元素。利用这种有序性,我们可以快速找出一个滑动窗口(比如连续 k 个数的子数组)中的最大值或最小值,效率比暴力扫描高得多。它常用于解决“滑动窗口最值”问题,是高效算法设计的利器。


一、什么是单调队列?—— 两条规矩的“超级队伍”

普通队列是先进先出,队伍里的人随意站着。单调队列额外加了两条规矩:

  1. 新来的人必须遵守顺序​​:如果队伍是单调递减(队首最大),那么新来的人必须比队尾的人矮(或相等),否则队尾的人会一个个被弹走,直到新来的人能排进去。
  2. 队首的人如果“过期”了(窗口滑出),就要离开​​:比如滑动窗口右移后,原来在窗口左边的人不再属于当前窗口,队首可能会被删除。

通过这两条规矩,队伍永远保持着单调有序,并且队首永远指向当前窗口的最值(最大值或最小值)。

生活中的类比​​:想象你每天放学去小卖部买冰淇淋,窗口每次只能看到 3 个人。老板想快速知道这 3 个人中谁最高。如果每次都要重新挨个比较,就很慢。但如果让排队的人随时调整成“从高到矮”的队形,那么队首就是最高的那个。新来一个人时,只需要把比他矮的人赶走,再排进来;窗口移动时,最左边的人如果不在窗口里了,就让他离开。这样每次看队首就知道答案。


二、单调队列如何解决“滑动窗口最大值”?

这是单调队列最经典的应用。题目:给定一个数组 arr 和一个整数 k,请输出每个长度为 k 的连续子数组中的最大值。

2.1 暴力法 vs 单调队列法

  • 暴力法​​:对每个窗口,遍历窗口内所有元素找最大值,时间复杂度 O(n*k),当 n 和 k 很大时会超时。
  • 单调队列法​​:每个元素最多入队一次、出队一次,时间复杂度 O(n),快得多。

2.2 核心思路——维护一个单调递减队列

我们用双端队列(deque)​ 来存储​元素的下标​(而不是值本身),这样既能知道值,又能判断下标是否在窗口内。队列内部保持​单调递减​:即从队首到队尾,对应的数组元素值依次减小。队首就是当前窗口的最大值。

操作步骤(以数组 [1,3,-1,-3,5,3,6,7],窗口大小 k=3 为例):

  1. 从左到右遍历数组,对于每个位置 i:
  • 移除过期元素​​:如果队首下标小于 i - k + 1(窗口左边界),说明它已经不在当前窗口内,从队首弹出。
  • 保持单调性​​:只要队尾元素对应的值 ≤ 当前元素 arr[i],就把队尾弹出(因为当前元素更大,且位置更靠右,它会在窗口里待得更久,更有可能成为后面的最大值)。注意:这里用 ≤ 是为了让重复值也保留最新的一个(实际可以保留任意一个,但通常用 ≤ 会弹出旧的,保留新的,避免重复元素阻塞)。
  • 加入当前元素​​:把下标 i 从队尾压入。
  • 记录答案​​:当 i >= k-1 时,窗口已经形成,队首下标对应的值就是当前窗口的最大值。

2.3 手动模拟一遍

数组 [1, 3, -1, -3, 5, 3, 6, 7],k=3,队列里存的是下标,我们看值。

i arr[i] 队列中的下标(对应值) 说明 窗口最大值
0 1 [0] (值1) 初始,只有第一个元素 未形成窗口
1 3 [1] (值3) 3 > 队尾1,弹出0,加入1 未形成窗口
2 -1 [1,2] (值3,-1) -1 ≤ 队尾3,直接加入 最大值3
3 -3 [1,2,3] (值3,-1,-3) -3 ≤ 队尾-1,加入 最大值3
4 5 [4] (值5) 5大于队尾-3、-1、3,全部弹出,加入4 最大值5
5 3 [4,5] (值5,3) 3 ≤ 队尾5,加入 最大值5
6 6 [6] (值6) 6大于队尾3和5,弹出后加入6 最大值6
7 7 [7] (值7) 7大于队尾6,弹出后加入7 最大值7

最终结果:[3, 3, 5, 5, 6, 7],与代码输出一致。


三、完整代码实现(含详细注释)

cpp
#include <iostream>
#include <deque>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 3, -1, -3, 5, 3, 6, 7}; // 原始数组
    int k = 3;                                     // 滑动窗口大小
    deque<int> dq;                                 // 双端队列,存元素下标
    vector<int> ans;                               // 存储每个窗口的最大值

    for (int i = 0; i < arr.size(); i++) {
        // 1. 移除不在当前窗口内的队首元素(下标小于左边界)
        if (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // 2. 保持单调递减:弹出队尾所有比当前元素小的(或等于的)
        while (!dq.empty() && arr[dq.back()] <= arr[i]) {
            dq.pop_back();
        }

        // 3. 当前元素下标入队(此时队列中所有元素都比它大或相等,它成为新队尾)
        dq.push_back(i);

        // 4. 当窗口完全覆盖前 k 个元素后,记录答案
        if (i >= k - 1) {
            ans.push_back(arr[dq.front()]); // 队首就是当前窗口的最大值
        }
    }

    // 输出结果
    for (int x : ans) {
        cout << x << " "; // 输出:3 3 5 5 6 7
    }
    cout << endl;

    return 0;
}

代码说明​​:

  • 使用 deque(双端队列)是因为我们需要从队首和队尾都能删除,从队尾插入。
  • 队列里存的是下标,这样我们可以通过 arr[dq.front()] 得到最大值,同时通过下标判断是否过期。
  • 循环中,每个元素最多入队一次、出队一次,总时间复杂度 O(n)。

四、常见错误与注意事项

  1. 忘记检查队首是否过期​​:如果不检查,当窗口左移后,队首可能已经不属于当前窗口,但还作为最大值输出,导致结果错误。
  2. 比较符号写反​​:求最大值时,应该弹出比当前元素小的(保持队首最大),所以判断条件是 arr[dq.back()] <= arr[i] 时弹出。如果要求最小值,则条件改为 >= 弹出比当前大的,保持队首最小。
  3. 队列里只存值不存下标​​:如果不存下标,就无法判断元素是否过期,也无法正确地弹出队尾(因为可能有重复值,只通过值无法唯一确定)。所以一定要存下标。
  4. 忘记初始化窗口​​:在 i < k-1 时不能记录答案,否则会输出不完整的窗口结果。
  5. 对空队列进行操作​​:在 pop_front 和 pop_back 前一定要检查 !dq.empty(),否则会崩溃。

五、单调队列的另一种口味:单调递增队列

单调递减队列用来求窗口最大值,那如果想求窗口最小值呢?只要把比较符号反过来,让队列保持单调递增(队首最小):

  • 弹出条件:arr[dq.back()] >= arr[i](队尾比当前大就弹出)
  • 这样队首总是最小的。

比如求 [1,3,-1,-3,5,3,6,7] 的每个长度为 3 的窗口最小值,结果应该是:[-1,-3,-3,-3,3,3]。你可以试着用单调递增队列模拟一下。


六、相关知识点指引

  • 单调栈​​:与单调队列类似,但只能从一端操作(栈顶)。用于解决“下一个更大元素”等类型的问题。
  • 优先队列(堆)​​​:也可以求滑动窗口最值,但需要支持删除任意元素,实现复杂些(懒删除),而单调队列在顺序滑动时更简洁高效。
  • 双端队列(deque)​​​:单调队列的底层数据结构,需要熟练掌握其常用操作(push_back, pop_front, pop_back, front, back)。

单调队列就像一支训练有素的队伍,时刻保持有序,让你一眼就能找出队伍里最“突出”的那一位。掌握了它,处理滑动窗口最值问题就不再是难题了。

同类知识点