信奥赛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;}

信奥赛C++提高组csp-s之单调队列详解