信奥赛C++提高组csp-s之单调队列详解
信奥赛C++提高组csp-s之单调队列详解
一、基本概念
单调队列是一种特殊的队列数据结构，其内部元素始终保持单调递增或单调递减的特性。核心用途是高效解决滑动窗口类问题，例如在 O(n) 时间复杂度内找到所有窗口的最大/最小值。
二、核心特性
- 单调性：队列内元素保持严格单调递增或递减。
- 时效性：及时移除超出窗口范围的元素。
- 高效维护：每个元素入队一次、出队一次，时间复杂度 O(n)。
三、应用场景
- 滑动窗口最大值/最小值
- 限制区间最值问题
- 优化动态规划中的状态转移
研究案例： 滑动窗口 /【模板】单调队列
题目描述
给定一个长度为n的数组和一个固定大小的窗口k，窗口从数组最左端滑动到最右端。要求输出每个窗口中的最小值和最大值。
输入示例
8 3 1 3 -1 -3 5 3 6 7输出示例
-1 -3 -3 -3 3 3 3 3 5 5 6 7解题思路
- 维护一个单调递减队列，队头始终是当前窗口最大值
- 遍历数组时：
- 移除队头过期元素（超出窗口范围）
- 从队尾移除比当前元素小的元素
- 将当前元素索引加入队列
- 记录窗口最大值/最小值
代码实现（数组模拟单调队列）
#include<cstdio>usingnamespacestd;constintMAXN=1e6+10;inta[MAXN],q[MAXN];// 数组和单调队列（存储下标）intn,k;voidgetMin(){inthead=1,tail=0;// 队列头尾指针for(inti=1;i<=n;i++){// 删除超出窗口的队头元素while(head<=tail&&q[head]<i-k+1)head++;// 维护单调递增性（队尾比当前元素大则删除）while(head<=tail&&a[i]<=a[q[tail]])tail--;q[++tail]=i;// 当前元素下标入队// 从第k个元素开始输出if(i>=k)printf("%d ",a[q[head]]);}printf("\n");}voidgetMax(){inthead=1,tail=0;// 队列头尾指针for(inti=1;i<=n;i++){// 删除超出窗口的队头元素while(head<=tail&&q[head]<i-k+1)head++;// 维护单调递减性（队尾比当前元素小则删除）while(head<=tail&&a[i]>=a[q[tail]])tail--;q[++tail]=i;// 当前元素下标入队// 从第k个元素开始输出if(i>=k)printf("%d ",a[q[head]]);}printf("\n");}intmain(){scanf("%d %d",&n,&k);for(inti=1;i<=n;i++)scanf("%d",&a[i]);getMin();// 输出所有窗口的最小值getMax();// 输出所有窗口的最大值return0;}关键代码解析
队列初始化
inthead=1,tail=0;使用数组模拟队列，
head和tail分别表示队列头和尾的指针。移除过期元素
while(head<=tail&&q[head]<i-k+1){head++;}当队头元素索引超出当前窗口左边界时（计算方式：
i - k + 1），将其移出队列。维护单调性
while(head<=tail&&a[i]>=a[q[tail]]){tail--;}从队尾向前删除所有小于等于当前元素的索引，保证队列单调递减。
记录结果
if(i>=k-1){cout<<a[q[head]]<<" ";}当遍历到第 k 个元素时开始输出，此时队列头即为当前窗口最大值。
重点强调
双队列策略
getMin()：维护单调递增队列，队头始终是窗口最小值getMax()：维护单调递减队列，队头始终是窗口最大值
队列维护核心操作
while(head<=tail&&q[head]<i-k+1)head++;// 清除过期元素while(head<=tail&&a[i]<=a[q[tail]])tail--;// 维护单调性q[++tail]=i;// 入队新元素时间复杂度
- 每个元素入队、出队各一次，总时间复杂度O(n)
- 空间复杂度O(n)
关键点总结
- 单调队列本质：通过及时淘汰无用数据，将求极值的复杂度从 O(nk) 优化到 O(n)
- 窗口边界判断：
i - k是窗口左边界的前一个位置 - 队列存储索引：既能判断元素位置是否过期，又能直接访问原数组值
更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}