P1886 滑动窗口 /【模板】单调队列（单调队列）

滑动窗口 /【模板】单调队列

题目传送门

解题思路

这题就是一道模板题目，我们可以直接用单调队列的单调递增和单调递减来做
单调队列

AC代码

#include<iostream>
#include<cstdio>
using namespace std;
long long n,k,o1,o2,head1,head2,tail1,tail2,a[1000005],b1[1000005],b2[1000005],q1[1000005],q2[1000005],p1[1000005],p2[1000005];
int main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++)
	 scanf("%lld",&a[i]);
	q1[1]=q2[1]=a[1]; //初始化
	p1[1]=p2[1]=head1=head2=tail1=tail2=1;
	if(k==1)b1[++o1]=b2[++o2]=a[1];//特判
	for(int i=2;i<=n;i++)
	{
		while(a[i]<=q1[tail1]&&head1<=tail1)tail1--;//单调递增（求最小值）
		q1[++tail1]=a[i];
		p1[tail1]=i;
		while(i-p1[head1]>=k)head1++;
		if(i>=k)b1[++o1]=q1[head1];
		
		while(q2[tail2]<=a[i]&&head2<=tail2)tail2--;//单调递减（求最大值）
		q2[++tail2]=a[i];
		p2[tail2]=i;
		while(i-p2[head2]>=k)head2++;
		if(i>=k)b2[++o2]=q2[head2];
	} 
	for(int i=1;i<=o1;i++)//输出
	 printf("%lld ",b1[i]);
	printf("\n");
	for(int i=1;i<=o2;i++)
	 printf("%lld ",b2[i]); 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

谢谢