目录
- 一、单调队列的核心思想与本质
- 二、单调队列的应用场景
- 1. 滑动窗口最大值
- 2. 区间最值查询
- 3. 优化动态规划
- 三、单调队列的实现与优化
- 1. 双端队列的选择
- 2. 单调性的维护
- 3. 空间压缩
- 四、单调队列的复杂度分析
- 五、单调队列的变种与高阶应用
- 1. 二维单调队列
- 2. 带限制的滑动窗口
- 3. 多队列协作
- 六、常见陷阱与调试技巧
- 1. 边界条件处理
- 2. 调试方法
- 七、代码模版
- 八、经典例题
- [滑动窗口 /【模板】单调队列](https://www.luogu.com.cn/problem/P1886)
- 单调队列
- MAX最值差
- 九、总结与学习建议
- 1. 核心总结
- 2. 学习建议
一、单调队列的核心思想与本质
核心思想：通过维护队列的单调性，快速获取区间内的最值信息，避免重复遍历。
本质：利用双端队列（Deque）动态维护一个单调递增或递减的序列，支持高效查询和更新。
二、单调队列的应用场景
1. 滑动窗口最大值
问题描述：给定数组 nums 和窗口大小 k，返回每个窗口的最大值。
单调队列解法：维护一个单调递减队列，队首为当前窗口最大值：
from collections import dequedef maxSlidingWindow(nums, k):q = deque()res = []for i, num in enumerate(nums):# 移除队尾小于当前元素的元素while q and nums[q[-1]] < num:q.pop()# 将当前元素下标加入队尾q.append(i)# 移除队首超出窗口范围的元素while q[0] <= i - k:q.popleft()# 队首为当前窗口最大值if i >= k - 1:res.append(nums[q[0]])return res
2. 区间最值查询
问题描述：动态查询数组中任意区间的最小值或最大值。
单调队列解法：通过滑动窗口维护区间最值，适用于固定窗口大小的问题。
3. 优化动态规划
问题描述：在动态规划中，状态转移方程涉及区间最值查询时，单调队列可以优化时间复杂度。
示例：LeetCode 1696. 跳跃游戏 VI。
三、单调队列的实现与优化
1. 双端队列的选择
Python：使用 collections.deque，支持高效的头尾操作。
C++：使用 std::deque 或手写双端队列。
Java：使用 ArrayDeque。
2. 单调性的维护
单调递增队列：队首为最小值，队尾为最大值。
单调递减队列：队首为最大值，队尾为最小值。
3. 空间压缩
存储下标而非值：通过下标可同时访问元素值和位置信息，减少空间占用。
结果数组复用：在部分问题中，直接修改原数组或复用结果数组。
四、单调队列的复杂度分析
时间复杂度
每个元素入队一次：遍历时每个元素被压入队列一次。
每个元素最多出队一次：一旦被弹出，后续不再处理。
总操作次数：
2n→O(n)。
空间复杂度
最坏情况：数组完全单调（如严格递增），队列空间为
O(n)。
优化后：多数问题中队列空间远小于 n
五、单调队列的变种与高阶应用
1. 二维单调队列
问题描述：在二维矩阵中查询子矩阵的最值。
实现思路：对每一行或每一列分别使用单调队列，再结合滑动窗口。
2. 带限制的滑动窗口
问题描述：在滑动窗口中增加额外限制条件（如窗口内元素和不超过某值）。
实现思路：结合前缀和与单调队列，动态维护窗口状态。
3. 多队列协作
问题描述：在复杂问题中，可能需要同时维护多个单调队列（如最大值队列和最小值队列）。
示例：LeetCode 239. 滑动窗口最大值。
六、常见陷阱与调试技巧
1. 边界条件处理
空队列检查：在弹出队首前需判断队列是否为空。
窗口范围检查：确保队首元素始终在窗口范围内。
2. 调试方法
打印队列状态：在每次入队/出队时输出队列内元素。
可视化遍历过程：手动画出元素处理顺序和队列变化。
七、代码模版
#include<iostream>
#include<deque>
using namespace std;#define maxn 100001;template<typename T>
bool max(T a, T b) {return a <= b;
}template<typename T>
bool min(T a, T b) {return a >= b;
}template<typename T>
void findIntervalMinMax(int n, int k, T h[], int ans[],bool (*cmp)(T a, T b)) {deque<int>q;for (int i = 0; i < n; i++) {while (!q.empty() && cmp(h[q.back()], h[i])) {q.pop_back();}q.push_back(i); while (q.back() - q.front() + 1 > k) {q.pop_front();}ans[i] = h[q.front()];}
}int main() {int h[] = { 8,7,6,9,11 };int ans[10];findIntervalMinMax(5, 3, h, ans, max);for (int i = 0; i < 5; i++) {cout << ans[i] << ' ';}cout << endl;findIntervalMinMax(5, 3, h, ans, min);for (int i = 0; i < 5; i++) {cout << ans[i] << ' ';}cout << endl;return 0;
}
八、经典例题
滑动窗口 /【模板】单调队列
#include<iostream>
#include<deque>
using namespace std;#define maxn 1000001template<typename T>
bool max(T a, T b) {return a <= b;
}template<typename T>
bool min(T a, T b) {return a >= b;
}template<typename T>
void findIntervalMaxMin(int n, int k, T h[], int ans[], bool (*cmp)(T a, T b)) {deque<int>q;for (int i = 0; i < n; i++) {while (!q.empty() && cmp(h[q.back()], h[i])) {q.pop_back();}q.push_back(i);while (q.back() - q.front() + 1 > k) {q.pop_front();}ans[i] = h[q.front()];}}int h[maxn], ans[maxn];int main() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++) {cin >> h[i];}findIntervalMaxMin(n, k, h, ans, min);for (int i = k - 1; i < n; i++) {cout << ans[i] << ' ';}cout << endl;findIntervalMaxMin(n, k, h, ans, max);for (int i = k - 1; i < n; i++) {cout << ans[i] << ' ';}cout << endl;return 0;
}
单调队列
#include<iostream>
#include<deque>
using namespace std;#define maxn 1000001template<typename T>
bool max(T a, T b) {return a <= b;
}template<typename T>
bool min(T a, T b) {return a >= b;
}template<typename T>
void findIntervalMaxMin(int n, int k, T h[], int ans[], bool (*cmp)(T a, T b)) {deque<int>q;for (int i = 0; i < n; i++) {while (!q.empty() && cmp(h[q.back()], h[i])) {q.pop_back();}q.push_back(i);while (q.back() - q.front() + 1 > k) {q.pop_front();}ans[i] = h[q.front()];}}int h[maxn], ans[maxn];int main() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++) {cin >> h[i];}findIntervalMaxMin(n, k, h, ans, min);for (int i = k - 1; i < n; i++) {cout << ans[i] << ' ';}cout << endl;findIntervalMaxMin(n, k, h, ans, max);for (int i = k - 1; i < n; i++) {cout << ans[i] << ' ';}cout << endl;return 0;
}
MAX最值差
#include<iostream>
#include<deque>
using namespace std;#define maxn 1000001template<typename T>
bool max(T a, T b) {return a <= b;
}template<typename T>
bool min(T a, T b) {return a >= b;
}template<typename T>
void findIntervalMaxMin(int n, int k, T h[], int ans[], bool (*cmp)(T a, T b)) {deque<int>q;for (int i = 0; i < n; i++) {while (!q.empty() && cmp(h[q.back()], h[i])) {q.pop_back();}q.push_back(i);while (q.back() - q.front() + 1 > k) {q.pop_front();}ans[i] = h[q.front()];}}int h[maxn], ans[maxn], ans1[maxn], ans2[maxn];int main() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++) {cin >> h[i];}findIntervalMaxMin(n, k, h, ans1, min);findIntervalMaxMin(n, k, h, ans2, max);int max = -1000000000;for (int i = 0; i < n; i++) {ans[i] = ans2[i] - ans1[i];if (ans[i] > max)max = ans[i];}cout << max << endl;return 0;
}
九、总结与学习建议
1. 核心总结
单调队列的核心是利用单调性快速获取区间最值，适合解决滑动窗口类问题。
高阶问题的突破口通常在于维度转换（如二维转一维）或逻辑等价变形。
2. 学习建议
分类刷题：按问题类型集中练习（如滑动窗口、区间最值、动态规划优化）。
对比暴力解法：理解单调队列如何减少重复计算。
手写模拟过程：在纸上画出队列的变化，加深直观理解。
通过以上分析，单调队列作为一种高效的数据结构，在解决区间最值查询和滑动窗口问题时具有显著优势。掌握其核心思想和实现技巧，能够大幅提升算法效率。
希望大家可以一键三连，后续我们一起学习，谢谢大家！！！
