【POJ2823】Sliding Window(单调队列的原理和简单应用)

Categories: 数据结构和算法
Comments: No Comments
Published on: 2011 年 05 月 05 日

单调递减队列是这么一个队列,它的头元素一直是队列当中的最大值,而且队列中的值是按照递减的顺序排列的。我们可以从队列的末尾插入一个元素,可以从队列的两端删除元素。

1.首先看插入元素:为了保证队列的递减性,我们在插入元素v的时候,要将队尾的元素和v比较,如果队尾的元素不大于v,则删除队尾的元素,然后继续将新的队尾的元素与v比较,直到队尾的元素大于v,这个时候我们才将v插入到队尾。

2.队尾的删除刚刚已经说了,那么队首的元素什么时候删除呢?由于我们只需要保存i的前k-1个元素中的最大值,所以当队首的元素的索引或下标小于i-k+1的时候,就说明队首的元素对于求f(i)已经没有意义了,因为它已经不在窗里面了。所以当index[队首元素] void de_increase(bool flag){ memset(Mqueues,0,sizeof(Mqueues)); last=first=1; Mqueues[last++].index=1; ansmax[1]=Sequence[1]; for (i=2;i<=n;i++){ if(flag) while(Sequence[Mqueues[last-1].index]<Sequence[i] && first<last) else while(Sequence[Mqueues[last-1].index]>Sequence[i] && first<last) last--; Mqueues[last++].index=i; while(Mqueues[first].index<i-k+1) first++; ansmax[i]=Sequence[Mqueues[first].index]; } }

#include <cstdio>
#include <cstring>
#define maxlen 1000005
struct Mqueue{
	int index;
}Mqueues[maxlen];
int Sequence[maxlen],ansmin[maxlen],ansmax[maxlen];
int n,k,i,j,temp,last,first;
void decrease(){
	memset(Mqueues,0,sizeof(Mqueues));
	last=first=1;
	Mqueues[last++].index=1;
	ansmax[1]=Sequence[1];
	for (i=2;i<=n;i++){
		while(Sequence[Mqueues[last-1].index]<Sequence[i] && first<last)
			last--;
		Mqueues[last++].index=i;
		while(Mqueues[first].index<i-k+1)
			first++;
		ansmax[i]=Sequence[Mqueues[first].index];
	}
}
void increase(){
	memset(Mqueues,0,sizeof(Mqueues));
	last=first=1;
	Mqueues[last++].index=1;
	ansmin[1]=Sequence[1];
	for (i=2;i<=n;i++){
		while(Sequence[Mqueues[last-1].index]>Sequence[i] && first<last)
			last--;
		Mqueues[last++].index=i;
		while(Mqueues[first].index<i-k+1)
			first++;
		ansmin[i]=Sequence[Mqueues[first].index];
	}
}
int main(){
	//freopen("1.txt","r",stdin);
	scanf("%d%d",&n,&k);
	for (i=1;i<=n;i++)
		scanf("%d",&Sequence[i]);
	decrease();
	increase();
	for (int i=k;i<=n;i++)
		printf("%d ",ansmin[i]);
	printf("\n");
	for (int i=k;i<=n;i++)
		printf("%d ",ansmax[i]);
	printf("\n");
}
个人原创,转载请注明:三江小渡

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日