30、.NET泛型与服务器端电子表格开发详解
2025/12/26 10:20:50
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) 时间内获取队列中的最值，同时维护队列的单调性。
算法流程
求最小值（维护单调递增队列）：
- 队列中存储元素的索引，而不是值本身
- 维护队列使得队首到队尾对应的值单调递增
- 每次滑动窗口：
- 移除队首超出窗口范围的元素
- 从队尾移除比当前元素大的元素，保持单调性
- 将当前元素索引加入队尾
- 当窗口形成时，输出队首对应的值
求最大值（维护单调递减队列）：
- 与最小值类似，但维护队首到队尾对应的值单调递减
- 从队尾移除比当前元素小的元素
时间复杂度：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（双端队列）：能在两端进行插入删除操作，符合单调队列需求
- 存储索引而非值：便于判断元素是否在窗口内，也方便获取对应值
两个关键维护操作
窗口范围维护：
while(!dq.empty()&&dq.front()<=i-k){dq.pop_front();}- 确保队列中所有元素都在当前窗口内
- 只需检查队首，因为队列是按时间顺序加入的
单调性维护：
- 最小值：移除队尾所有 ≥ a[i] 的元素
- 最大值：移除队尾所有 ≤ a[i] 的元素
- 保证队列的单调性质，队首就是当前窗口的最值
输出时机
当i >= k-1时，窗口完全进入数组，可以输出结果。此时共有n-k+1个窗口。
算法优势
- 高效：每个元素最多入队出队一次，O(n) 时间复杂度
- 空间优化：只需 O(k) 的额外空间
- 通用性强：模板化代码，适用于各种滑动窗口最值问题
示例分析
以输入[1,3,-1,-3,5,3,6,7]，k=3为例：
最小值队列变化：
- i=0(1): 队列[0] → 无输出
- i=1(3): 队列[0,1] → 无输出
- i=2(-1): 移除1，队列[0,2] → 输出 a[2]=-1
- i=3(-3): 移除2，队列[3] → 输出 a[3]=-3
- i=4(5): 队列[3,4] → 输出 a[3]=-3
- i=5(3): 移除4，队列[3,5] → 输出 a[3]=-3
- i=6(6): 移除3，队列[5,6] → 输出 a[5]=3
- 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;}