滑动窗口 /【模板】单调队列
题目描述
有一个长为 \(n\) 的序列 \(a\)，以及一个大小为 \(k\) 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如，对于序列 \([1,3,-1,-3,5,3,6,7]\) 以及 \(k = 3\)，有如下过程：
\[\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} \]输入格式
输入一共有两行，第一行有两个正整数 \(n,k\)。
第二行 \(n\) 个整数，表示序列 \(a\)
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
样例 #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\%\) 的数据，\(1 \le n \le 10^5\)；
对于 \(100\%\) 的数据，\(1\le k \le n \le 10^6\)，\(a_i \in [-2^{31},2^{31})\)。
#include<bits/stdc++.h>
using namespace std;
int x;
struct sd
{
int num,val; //存储编号和大小
};
deque<sd> que;
deque<sd> que1;
int add[3][1000005]; //用以存储答案的----见代码
int main()
{
int n,m,k,cnt=1;
cin>>n>>k;
sd rr;
for(int i=1;i<=n;i++)
{
scanf("%d",&x); //输入
rr.num=i; rr.val=x; //赋值
while(!que.empty()&&x>=que.back().val)
que.pop_back(); //单调队列的操作，以保证单调
while(!que1.empty()&&x<=que1.back().val)
que1.pop_back();
que.push_back(rr); //压入队列
que1.push_back(rr);//同上
while(i-k>=que.front().num) //T掉不在范围内的
que.pop_front();
while(i-k>=que1.front().num)
que1.pop_front(); //同上
if(i>=k)
{
add[0][cnt]=que.front().val;
add[1][cnt]=que1.front().val;
cnt++;
} //存答案
}
for(int i=1;i<cnt;i++)
printf("%d ",add[1][i]);
printf("\n");
for(int i=1;i<cnt;i++)
printf("%d ",add[0][i]); //输出
return 0;
}
1 d[i]//:返回d中下标为I的元素的引用。
2 d.front()//:返回的一个元素的引用。
3 d.back()//:返回最后一个元素的引用。
4 d.pop_back()//:删除尾部的元素。不返回值。
5 d.pop_front()//：删除头部元素。不返回值。
6 d.push_back(e)//:在队尾添加一个元素e。
7 d.push_front(e)//:在对头添加一个元素e。