csp信奥赛C++标准模板库STL案例应用17
deque实践
题目描述
一个含有n nn项的数列，求出每一项前的m mm个数到它这个区间内的最小值。若前面的数不足m mm项则从第1 11个数开始，若前面没有数则输出0 00。
输入格式
第一行两个整数，分别表示n nn，m mm。
第二行，n nn个正整数，为所给定的数列a i a_iai。
输出格式
n nn行，每行一个整数，第i ii个数为序列中a i a_iai之前m mm个数的最小值。
输入输出样例 1
输入 1
6 2 7 8 1 4 3 2输出 1
0 7 7 1 1 3说明/提示
对于100 % 100\%100%的数据，保证1 ≤ m ≤ n ≤ 2 × 10 6 1\le m\le n\le2\times10^61≤m≤n≤2×106，1 ≤ a i ≤ 3 × 10 7 1\le a_i\le3\times10^71≤ai≤3×107。
思路分析
本题要求对每个位置i，找到区间[i-m, i-1]的最小值（如果区间不足m个元素，则从第一个元素开始）。这是一个典型的滑动窗口最小值问题。
核心算法：单调队列
使用一个双端队列维护一个递增的单调队列：
- 队列中存储数组元素的索引，这些索引对应的值保持单调递增
- 对于每个新元素，从队尾移除比它大的元素（保证队列单调性）
- 从队首移除超出窗口范围的元素
- 队首元素就是当前窗口的最小值
算法复杂度
- 时间复杂度：O(n)，每个元素最多入队和出队一次
- 空间复杂度：O(m)，队列中最多存储m个索引
代码实现
#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,m;cin>>n>>m;// 读取n和mvector<int>a(n+1);// 1-indexed数组，方便处理// 读取数组for(inti=1;i<=n;i++){cin>>a[i];}deque<int>dq;// 存储索引的单调队列（双端队列）// 第一个元素前面没有元素，输出0cout<<0<<'\n';// 处理从第1个到第n-1个元素（为后续元素提供窗口最小值）for(inti=1;i<n;i++){// 维护队列单调性：从队尾移除比当前元素大的元素// 因为当前元素比它们小且位置更靠后，所以这些元素不可能成为未来窗口的最小值while(!dq.empty()&&a[dq.back()]>=a[i]){dq.pop_back();}// 将当前元素索引加入队列dq.push_back(i);// 移除超出窗口范围的元素// 窗口范围是 [i-m+1, i]（对于下一轮i+1来说，需要的是[i-m+2, i+1]）// 但我们要为第i+1个元素找前m个元素的最小值，所以这里检查是否超出[i-m+1, i]while(!dq.empty()&&dq.front()<=i-m){dq.pop_front();}// 输出当前窗口的最小值（即为第i+1个元素前m个元素的最小值）// 如果队列为空，说明前面没有元素，输出0if(dq.empty()){cout<<0<<'\n';}else{cout<<a[dq.front()]<<'\n';}}return0;}功能分析
输入处理
- 第一行：读取n（数列长度）和m（窗口大小）
- 第二行：读取n个正整数到数组a[1…n]（使用1-indexed方便理解）
特殊处理
- 对于第一个元素（i=1）：前面没有元素，直接输出0
滑动窗口处理
- 队列初始化：开始时队列为空
- 单调性维护：
- 当新元素加入时，从队尾移除所有值大于等于它的元素
- 这样保证队列中的元素值严格递增
- 窗口范围维护：
- 移除队首超出当前窗口范围的元素（索引小于等于i-m）
- 输出结果：
- 队首元素即为当前窗口的最小值
- 如果队列为空，输出0
示例演示（输入样例）
输入：
6 2 7 8 1 4 3 2处理过程：
i=1: 输出0（第一个元素前无元素） i=1: 处理元素a[1]=7，队列为空→队列变为[1]，为a[2]准备窗口 窗口[1]，最小值a[1]=7，输出7 i=2: 处理元素a[2]=8，队尾a[1]=7<8→队列变为[1,2] 窗口[1,2]，最小值a[1]=7，输出7 i=3: 处理元素a[3]=1，队尾a[2]=8>=1→弹出2，队尾a[1]=7>=1→弹出1 队列变为[3] 窗口[2,3]，最小值a[3]=1，输出1 i=4: 处理元素a[4]=4，队尾a[3]=1<4→队列变为[3,4] 窗口[3,4]，最小值a[3]=1，输出1 i=5: 处理元素a[5]=3，队尾a[4]=4>=3→弹出4，队尾a[3]=1<3→队列变为[3,5] 窗口[4,5]，最小值a[3]=1，但索引3超出窗口[4,5]（3<=5-2=3）→弹出3 队列变为[5]，最小值a[5]=3，输出3输出：
0 7 7 1 1 3注意事项
- 使用
deque而不是普通队列，因为需要从两端操作 - 队列中存储索引而不是值，方便判断是否超出窗口范围
- 注意边界条件：当i=1时直接输出0，后续处理从i=1开始
- 时间复杂度必须为O(n)，不能使用O(nm)的暴力解法
完整系列资料，请查看专栏：《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;}
