csp信奥赛C++标准模板库STL案例应用16

csp信奥赛C++标准模板库STL案例应用16

deque实践

题目描述

有一个长为n nn的序列a aa，以及一个大小为k kk的窗口。现在这个窗口从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最小值和最大值。

例如，对于序列[ 1 , 3 , − 1 , − 3 , 5 , 3 , 6 , 7 ] [1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7]以及k = 3 k = 3k=3，有如下过程：

窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 − 1 3 1 [3 -1 -3] 5 3 6 7 − 3 3 1 3 [-1 -3 5] 3 6 7 − 3 5 1 3 -1 [-3 5 3] 6 7 − 3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 \def\arraystretch{1.2} \begin{array}{|c|c|c|}\hline \textsf{窗口位置} & \textsf{最小值} & \textsf{最大值} \\ \hline \verb![1 3 -1] -3 5 3 6 7 ! & -1 & 3 \\ \hline \verb! 1 [3 -1 -3] 5 3 6 7 ! & -3 & 3 \\ \hline \verb! 1 3 [-1 -3 5] 3 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 [-3 5 3] 6 7 ! & -3 & 5 \\ \hline \verb! 1 3 -1 -3 [5 3 6] 7 ! & 3 & 6 \\ \hline \verb! 1 3 -1 -3 5 [3 6 7]! & 3 & 7 \\ \hline \end{array}窗口位置[1 3 -1] -3 5 3 6 71 [3 -1 -3] 5 3 6 71 3 [-1 -3 5] 3 6 71 3 -1 [-3 5 3] 6 71 3 -1 -3 [5 3 6] 71 3 -1 -3 5 [3 6 7]​最小值−1−3−3−333​最大值335567​​

输入格式

输入一共有两行，第一行有两个正整数n , k n,kn,k；
第二行有n nn个整数，表示序列a aa。

输出格式

输出共两行，第一行为每次窗口滑动的最小值；
第二行为每次窗口滑动的最大值。

输入输出样例 1

输入 1

8 3 1 3 -1 -3 5 3 6 7

输出 1

-1 -3 -3 -3 3 3 3 3 5 5 6 7

说明/提示

【数据范围】
对于50 % 50\%50%的数据，1 ≤ n ≤ 1 0 5 1 \le n \le 10^51≤n≤105；
对于100 % 100\%100%的数据，1 ≤ k ≤ n ≤ 1 0 6 1\le k \le n \le 10^61≤k≤n≤106，a i ∈ [ − 2 31 , 2 31 ) a_i \in [-2^{31},2^{31})ai​∈[−231,231)。

思路分析

核心思想：单调队列

单调队列是一种数据结构，能在 O(1) 时间内获取队列中的最值，同时维护队列的单调性。

算法流程

求最小值（维护单调递增队列）：

1. 队列中存储元素的索引，而不是值本身
2. 维护队列使得队首到队尾对应的值单调递增
3. 每次滑动窗口：
   • 移除队首超出窗口范围的元素
   • 从队尾移除比当前元素大的元素，保持单调性
   • 将当前元素索引加入队尾
   • 当窗口形成时，输出队首对应的值

求最大值（维护单调递减队列）：

1. 与最小值类似，但维护队首到队尾对应的值单调递减
2. 从队尾移除比当前元素小的元素

时间复杂度：O(n)

每个元素最多入队出队一次，因此总时间复杂度为 O(n)。

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=1e6+5;inta[MAXN];intmain(){intn,k;cin>>n>>k;for(inti=0;i<n;i++){cin>>a[i];}deque<int>dq;// 双端队列，存储元素索引// ---------- 求最小值 ----------for(inti=0;i<n;i++){// 移除队首超出窗口范围的元素// 如果队首索引小于等于 i-k，说明该元素已不在当前窗口中while(!dq.empty()&&dq.front()<=i-k){dq.pop_front();}// 维护单调递增队列（从队首到队尾，a[索引]递增）// 从队尾开始，移除所有大于等于当前元素 a[i] 的索引// 因为这些元素不可能成为后续窗口的最小值（有更小的 a[i]）while(!dq.empty()&&a[dq.back()]>=a[i]){dq.pop_back();}// 将当前索引加入队尾dq.push_back(i);// 当窗口完全进入数组后开始输出（已经处理了至少 k 个元素）// 此时队首元素就是当前窗口的最小值if(i>=k-1){cout<<a[dq.front()]<<" ";}}cout<<endl;// 清空队列，准备求最大值dq.clear();// ---------- 求最大值 ----------for(inti=0;i<n;i++){// 同样先移除超出窗口的元素while(!dq.empty()&&dq.front()<=i-k){dq.pop_front();}// 维护单调递减队列（从队首到队尾，a[索引]递减）// 从队尾开始，移除所有小于等于当前元素 a[i] 的索引// 因为这些元素不可能成为后续窗口的最大值（有更大的 a[i]）while(!dq.empty()&&a[dq.back()]<=a[i]){dq.pop_back();}dq.push_back(i);// 输出当前窗口的最大值if(i>=k-1){cout<<a[dq.front()]<<" ";}}cout<<endl;return0;}

功能分析

数据结构选择

• deque（双端队列）：能在两端进行插入删除操作，符合单调队列需求
• 存储索引而非值：便于判断元素是否在窗口内，也方便获取对应值

两个关键维护操作

1. 窗口范围维护：

   while(!dq.empty()&&dq.front()<=i-k){dq.pop_front();}

   • 确保队列中所有元素都在当前窗口内
   • 只需检查队首，因为队列是按时间顺序加入的

2. 单调性维护：

   • 最小值：移除队尾所有 ≥ a[i] 的元素
   • 最大值：移除队尾所有 ≤ a[i] 的元素
   • 保证队列的单调性质，队首就是当前窗口的最值

输出时机

当i >= k-1时，窗口完全进入数组，可以输出结果。此时共有n-k+1个窗口。

算法优势

1. 高效：每个元素最多入队出队一次，O(n) 时间复杂度
2. 空间优化：只需 O(k) 的额外空间
3. 通用性强：模板化代码，适用于各种滑动窗口最值问题

示例分析

以输入[1,3,-1,-3,5,3,6,7]，k=3为例：

最小值队列变化：

1. i=0(1): 队列[0] → 无输出
2. i=1(3): 队列[0,1] → 无输出
3. i=2(-1): 移除1，队列[0,2] → 输出 a[2]=-1
4. i=3(-3): 移除2，队列[3] → 输出 a[3]=-3
5. i=4(5): 队列[3,4] → 输出 a[3]=-3
6. i=5(3): 移除4，队列[3,5] → 输出 a[3]=-3
7. i=6(6): 移除3，队列[5,6] → 输出 a[5]=3
8. i=7(7): 队列[5,6,7] → 输出 a[5]=3

完整系列资料，请查看专栏：《csp信奥赛C++标准模板库STL》
https://blog.csdn.net/weixin_66461496/category_13108077.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

• 一、CSP信奥赛C++通关学习视频课：
  • C++语法基础
  • C++语法进阶
  • C++算法
  • C++数据结构
  • CSP信奥赛数学
  • CSP信奥赛STL
• 二、CSP信奥赛C++竞赛拿奖视频课：
  • 信奥赛csp-j初赛高频考点解析
  • CSP信奥赛C++复赛集训课（12大高频考点专题集训）
• 三、考级、竞赛刷题题单及题解：
  • GESP C++考级真题题解
  • CSP信奥赛C++初赛及复赛高频考点真题解析
  • CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

• 2025 csp-j 复赛真题及答案解析（最新更新）
• 2025 csp-x(山东) 复赛真题及答案解析（最新更新）
• 2025 csp-x(河南) 复赛真题及答案解析（最新更新）
• 2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
• 2025 csp-x(江西) 复赛真题及答案解析（最新更新）
• 2025 csp-x(广西) 复赛真题及答案解析（最新更新）
• 2020 ~ 2024 csp 复赛真题题单及题解
• 2019 ~ 2022 csp-j 初赛高频考点真题分类解析
• 2021 ~ 2024 csp-s 初赛高频考点解析
• 2023 ~ 2024 csp-x (山东)初赛真题及答案解析
• 2024 csp-j 初赛真题及答案解析
• 2025 csp-j 初赛真题及答案解析（最新更新）
• 2025 csp-s 初赛真题及答案解析（最新更新）
• 2025 csp-x (山东)初赛真题及答案解析(最新更新)
• 2025 csp-x (江西)初赛真题及答案解析(最新更新)
• 2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

• 129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、 前缀和、差分、深搜、广搜、DP专题、 树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}