POJ2823（单调队列方法解题）

因为不太好复制，我就直接截图了，题目链接；题目大致的意思是：给一串数字，然后要你求出每k长度的连续子序列中的最大值以及最小值并输出；这题就是一个最简单的运用单调队列方法解题的例子。

解题思路：通过单调队列，分别维护一个递增以及递减的数列以求得最小值和最大值（增减对应），其中用到了数组的游标删减，主要思想是通过一个f[]数组存储每次比较得出的最值，通过t[]数组存储游标（即变化的数组下标）；

代码：

#include<cstdio>
#include<cstdlib>
#include<memory.h>
#define Max_Size 1000000
int t[Max_Size];
int f[Max_Size];
int num[Max_Size];

int main()
{
	int n,k;
	int i,j;
	int min,max;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++)
	{
		scanf("%d",&num[i]);
	}
	int tail=0,front=0;
	for(i=0;i<n;i++)
	{
		while(front<tail&&f[tail-1]>num[i])tail--;                   //维护一个单调递增的序列，最后求得最小值； 
		f[tail]=num[i];                                                   //每次这个数要么替换f[]中的数，要么直接加入，因此始终都是要加入到队列中，对其大小处理在后一个过程中的while()中处理； 
		t[tail]=i;
		tail++;
		while(t[front]<=i-k)front++;
		if(i>k-2)                                       //每三个数都要输出其中的最小值（即从第三个数开始）； 
		{
			printf("%d%c",f[front],i==n-1?'
':' ');
		}
	}
	tail=0;front=0;
	memset(f,0,sizeof(f));
	memset(t,0,sizeof(t)); 
	for(i=0;i<n;i++)
	{
		while(front<tail&&f[tail-1]<num[i])tail--;
		f[tail]=num[i];
		t[tail]=i;
		tail++;
		while(t[front]<=i-k)front++;
		if(i>k-2)
		{
			printf("%d%c",f[front],i==n-1?'
':' ');
		}
	}
	return 0;
}

后续还有单调队列题目将会更新，并将链接附上；