单调队列模板题
有一个长为 nnn 的序列 aaa，以及一个大小为 kkk 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
例如：
The array is [1,3,−1,−3,5,3,6,7][1,3,-1,-3,5,3,6,7][1,3,−1,−3,5,3,6,7], and k=3k = 3k=3。
输入格式
输入一共有两行，第一行有两个正整数 n,kn,kn,k。 第二行 nnn 个整数，表示序列 aaa
输出格式
输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值
输入输出样例
输入 #1
8 3 1 3 -1 -3 5 3 6 7
输出 #1
-1 -3 -3 -3 3 3 3 3 5 5 6 7
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<deque>//双向队列
using namespace std;
const int maxn=2000010;
int n,m;
struct node
{
int val;
int pos;
}A[maxn];
deque<node> min_Q;
deque<node> min_X;
inline int rd()//快读模板
{
int data = 0;
int f = 1;
char ch = getchar();
while(ch < '0'||ch > '9')
{
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0'&&ch <= '9')
{
data = (data<<3) + (data<<1) + ch - '0';
ch = getchar();
}
return f * data;
}
int min_que[maxn];
int min_qre[maxn];
int main()
{
n=rd();
m=rd();
for(int i=1;i<=n;i++)
{
A[i].val=rd();
A[i].pos=i-1;
}
for(int i=1;i<=n;i++)
{
while(!min_Q.empty()&&min_Q.back().val>=A[i].val)//比当前数小的从后方移出双向队列
{
min_Q.pop_back();
}
min_Q.push_back(A[i]);
while(!min_Q.empty()&&min_Q.front().pos<i-m)//不在当前数量中的 从前方移出队列
{
min_Q.pop_front();
}
while(!min_X.empty()&&min_X.back().val<=A[i].val)
{
min_X.pop_back();
}
min_X.push_back(A[i]);
while(!min_X.empty()&&min_X.front().pos<i-m)
{
min_X.pop_front();
}
if(i>=m) min_que[i-m]=min_Q.front().val,min_qre[i-m]=min_X.front().val;//把当前的双向队列值加入两个数组中
}
for(int i=0;i<n-m+1;i++)
{
printf("%d ",min_que[i]);
}
printf("\n");
for(int i=0;i<n-m+1;i++)
{
printf("%d ",min_qre[i]);
}
} 
美团公司氛围 2112人发布