POJ 2823 Sliding Window（单调队列）

所谓单调队列，就是支持从队尾插入删除，队头查询的一种数据结构，虽然用途不是很广泛，但是对于某些问题如：在一个被不断刷新的缓存区中多次查询最小值（最大值）非常高效

构造方法：对于单调上升队列：每次从队尾入队一个元素，都从队尾起依次删除比当前元素大的元素，强制使队列单调

示例，POJ 2823 Sliding Window

/*
poj  2823
8012K	5344MS
*/ 

#include<cstdio>
#include<iostream>

#define MAXN 1000005
#define MAX_INT 2147483647

using namespace std;

int que_min[MAXN][2],que_max[MAXN][2],ans_min[MAXN],ans_max[MAXN];
//que二维数组，[][0]表示元素，[][1]表示元素在输入序列中的下标 
int main()
{
	//freopen("./2823.in" , "r" , stdin);
	int m,n,h_max = 0,t_max = 0,h_min = 0,t_min = 0,t;
	/*
	h_min   t_min
	h_max   t_max
	分别是两个单调队列的头尾指针 
	*/
	que_min[0][0] = -MAX_INT; que_max[0][0] = MAX_INT;
	scanf("%d %d",&n,&m);
	for(int i = 1;i <= n;i ++)
	{
		scanf("%d",&t);
		while(t <= que_min[t_min][0] && t_min >= h_min)
		//从尾端开始，删除所有比当前元素大的元素 
		{
			t_min --;
		}
		t_min ++;
		que_min[t_min][0] = t;
		que_min[t_min][1] = i;
		while(que_min[h_min][1] <= i - m)
		//从当前位置i开始，取最小值的范围只能是[i - m + 1 , i] 
		//删除不合法的元素
		{
			h_min ++;
		}
		ans_min[i] = que_min[h_min][0];
	
		//同理计算最大值 
		while(t >= que_max[t_max][0] && t_max >= h_max)
		//从尾端开始，删除所有比当前元素小的元素 
		{
			t_max --;
		}
		t_max ++;
		que_max[t_max][0] = t;
		que_max[t_max][1] = i;
		while(que_max[h_max][1] <= i - m)
		//从当前位置i开始，取最大值的范围只能是[i - m + 1 , i]
		//删除不合法的元素
		{
			h_max ++;
		}
		ans_max[i] = que_max[h_max][0];
	}
	
	for(int i = m;i <= n;i ++)
		printf("%d ",ans_min[i]);
	printf("\n");
	for(int i = m;i <= n;i ++)
		printf("%d ",ans_max[i]);
	printf("\n");
	return 0;
}