单调队列是双端队列，维护元素下标对应的值单调递减或递增，用于滑动窗口最值问题。1. 用std::deque存储下标，便于判断是否过期；2. 插入前从队尾删除小于当前值的下标，保持单调性；3. 队首超出窗口时移除；4. 从第k个元素开始记录结果。时间复杂度O(n)，优于暴力法。
在C++中，单调队列通常用于解决滑动窗口类问题，比如求滑动窗口最大值、最小值，或满足某种单调性要求的子数组问题。单调队列的核心思想是维护一个队列，使得其中的元素在值上保持单调递增或递减，同时保证下标顺序。
什么是单调队列
单调队列是一种双端队列（deque），它从队首到队尾的元素值保持单调性（递增或递减）。常见的是单调递减队列用于求最大值，单调递增队列用于求最小值。关键在于：每当我们加入一个新元素时，从队尾开始删除所有“不再有希望成为答案”的元素。
使用std::deque实现单调队列
我们可以借助C++标准库中的std::deque来高效实现单调队列。以下是一个求滑动窗口最大值的典型例子：
示例：滑动窗口最大值
立即学习“C++免费学习笔记（深入）”；
给定一个数组 nums 和窗口大小 k，输出每个窗口内的最大值。
#include#include using namespace std; vector maxSlidingWindow(vector & nums, int k) { deque dq; // 存储数组下标，保证对应值单调递减 vector result; for (int i = 0; i < nums.size(); ++i) { // 移除超出窗口范围的下标（队首） if (!dq.empty() && dq.front() == i - k) dq.pop_front(); // 从队尾移除所有小于当前元素的值的下标 while (!dq.empty() && nums[dq.back()] < nums[i]) dq.pop_back(); // 当前元素下标入队 dq.push_back(i); // 窗口形成后，队首就是当前窗口最大值的下标 if (i >= k - 1) result.push_back(nums[dq.front()]); } return result; }
关键操作说明
上述代码的关键点如下：
- 存储下标而非值：便于判断元素是否还在窗口内。
- 维护单调性：每次插入前，从队尾删除所有对应值小于当前值的下标，确保队列单调递减。
- 处理过期元素：当队首下标超出窗口左边界时，将其弹出。
- 结果收集时机：从第k个元素开始（即 i >= k-1），每个位置都可以输出一个窗口最大值。
扩展：单调递增队列（求最小值）
如果要维护单调递增队列以获取窗口最小值，只需修改比较条件：
```cpp while (!dq.empty() && nums[dq.back()] > nums[i]) dq.pop_back(); ```其余逻辑保持一致。
基本上就这些。掌握单调队列的关键是理解“用空间换优势”——通过维护一个结构，把O(nk)暴力优化到O(n)。核心是双端队列的操作和单调性的维护。不复杂但容易忽略细节。
