单调队列(洛谷p1886）模板题_洛谷1886

例题：洛谷p1886滑动窗口

有一个长为 n的序列 a，以及一个大小为 k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如：

The array is [1,3,-1,-3,5,3,6,7]， and k = 3。

单调队列有两个性质

1.队列中的元素其对应在原来的列表中的顺序必须是单调递增的。

2.队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)

单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队，也可以从队尾出队。

分析

以最小值为例：构造一个单调队列q[i]，记h为元素下标，q中存下标。第一次：q={1}；第二次：q={1,2}（因为3>1且在范围内）；第三次：q={3}（因为队列单调递增，-1最小，所以挤掉1和3，找最小值的时候也不会轮到它们）；第四次：q={4}（1已经在外面了。-3<-1果断挤掉）；第五次：q={4,5}（5>-3 可以作为候选人）；第六次：q={4,6}（果断挤掉，有比5合适的候选人）；第七次：b={6,7}（4不在范围内，出列）；第八次：b={6,7,8}

每次都输出队列中的第一个元素**(因为每次只有满足待入队的元素比队列中队尾元素更大才可以入队，否则需要将比它小的所有队列中的元素全部出队，再将它入队，因此队列始终单调递增，不可能存在比第一个元素更小的元素）**。

以此维护队列中元素序号的单调性，得到结果。

只是比较判断，时间复杂度很小。

相等的值也要挤掉。

最大值同理。
上代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath> 
using namespace std;
int n,k;
int q1[1000001],q2[1000001];
int a[1000001];
int min_deque()//求窗口内最小值 
{
	int l=1,r=0;//初始化队列左右下标（l为左，为右），只有这样初始化，l<=r才可以保证队列不为空。） 
	for(int i=1;i<=n;i++)
	{
		while(l<=r&&q1[l]+k<=i) l++;// q1[l]+k<=i表明队首元素已经不在窗口内，应将队首出列 
		while(l<=r&&a[i]<a[q1[r]]) r--;//若待入队元素比 队尾元素小，队尾出队，直到队内没有比它再大的元素为止，保证队列的单调递增 
		q1[++r]=i;//入队 
		if(i>=k) printf("%d ",a[q1[l]]);//当i<k时，说明窗口大小没有达到k，不会有输出，当i>=k后,每次窗口滑动都应输出队首 
	}
	cout<<endl;//不要忘记换行 
}
int max_deque()//求窗口内的最大值，步骤类似最小值 
{
	int l=1,r=0;
	for(int i=1;i<=n;i++)
	{
		while(l<=r&&q2[l]+k<=i) l++;
		while(l<=r&&a[i]>a[q2[r]]) r--;
		q2[++r]=i;
		if(i>=k) printf("%d ",a[q2[l]]);
	}
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	min_deque();
	max_deque();
	return 0;
}//自认为码风还是比较简洁的(#^.^#) 
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
33
34
35
36
37
38
39
40
41