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

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

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

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

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

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

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

生活中的类比：想象你每天放学去小卖部买冰淇淋，窗口每次只能看到 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 为例）：

从左到右遍历数组，对于每个位置 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]，与代码输出一致。

三、完整代码实现（含详细注释）

#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)。

四、常见错误与注意事项

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

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

例题精讲