欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

滑动窗口--单调队列

程序员文章站 2024-02-21 14:23:46
...

题目
滑动窗口--单调队列

Input
输入有两行。第一行两个整数n和k分别表示数列的长度和滑动窗口的大小,1<=k<=n<=1000000。第二行有n个整数表示ZJM的数列。

Output
输出有两行。第一行输出滑动窗口在从左到右的每个位置时,滑动窗口中的最小值。第二行是最大值。

Sample Input
8 3
1 3 -1 -3 5 3 6 7

Sample Output
-1 -3 -3 -3 3 3
3 3 5 5 6 7

解题思路
1.数据太大,暴力做法不可取。

2.维护局部单调性,所以我们可以考虑单调队列

3.写2个单调队列,一个是单调递增,一个单调递减

4.我们把元素加入到队列里面,要第 k 次后,才开始存储最大(最小)值。

代码实现

#include<cstdio>
#define Max 1000000
int n,k;  //数列长度和窗口大小

struct Pair{ 
	int index,ele;   //装索引和值
};

Pair a[Max];   //原数列
Pair q1[Max];  //取最小 ,队列
Pair q2[Max];  //取最大 ,队列
int ma[Max];   //装最大值
int mi[Max];  //装最小值
int mai,mii;  //对应上面两个的索引

void qu1();
void qu2();


int main()
{
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++) 
	{
		scanf("%d",&a[i].ele);
		a[i].index = i;
	}
	qu1();
	qu2();
	printf("%d",mi[0]);
	for(int i=1;i<mii;i++) printf(" %d",mi[i]);
	printf("\n%d",ma[0]);
	for(int i=1;i<mai;i++) printf(" %d",ma[i]);
	
	return 0;
}

void qu1()   //求最小的 
{
	int head=0,tail=-1;    //头尾指针
	bool flag = 0;   
	int count=0;
	for( int i=0;i<n;i++ )
	{          //i-q1[head].index+1是此时区间的大小
			//如果大小超过了k ,那么就把头弹出去
		while( head <= tail && i-q1[head].index+1 > k)
			head++;
		while(head<=tail && q1[tail].ele > a[i].ele )
			tail--;
			//维护区间的单调增减性,如果装入元素比队尾的小
			//那么就把队尾弹出去
		q1[++tail] = a[i];  //入队
		count++;     //计数器
		if( count == k ) //当窗口到达大小k时,就可以装入mi里面了
		flag = 1;
		if(flag)  mi[mii++] = q1[head].ele;
		//因为队列单调递增,所以头都是该窗口的最小值
	}
}

void qu2()   //同qu1类似
{
	int head = 0,tail = -1;
	int count = 0;
	bool flag = 0;
	for(int i=0;i<n;i++)
	{
		while( head <= tail && i-q2[head].index+1 > k )
		 head ++;
		while(head <= tail && q2[tail].ele < a[i].ele)
		 tail--;
		q2[++tail] = a[i] ;
		count++;
		if(count == k)
		flag=1;
		if(flag)
		ma[mai++] = q2[head].ele;
	}
}

小结
利用单调队列减少了复杂度,每个元素只进了队列2次,便分别求出了最大最小数组,如果用暴力求解,则会有非常多的元素被重复判断。