首页 > 代码库 > POJ 2823 Sliding Window 单调队列题解

POJ 2823 Sliding Window 单调队列题解

本题是单调队列题解的入门,当然也可以使用RMQ 和 线段树,不过速度都没有单调队列那么快。

单调队列难点:

1 如何入列,保存数据 -- 最小单调队列的时候, 所有数都入列一次,在新的数据准备入列的时候,增加判断,如果当前数值小于队尾数值,那么队尾数值就出列。空队列的时候直接入列。

2 保存的数列是什么样的?

举例吧: 1 3 -1 -3 5 3 6 7

构建最小单调队列

第一个数值1的时候,空队列,那么入列,得到: 1

第二个数值3, 因为大于1;那么1不用出列,直接入列,得到: 1 3

第三个数值-1,因为小于3,故此3出列,-1入列,继续判断-1小于1,故此1也出列,剩下队列得到: -1

以此类推……

根据实际情况,本题需要的是K大小端中的最小和最大值,那么就可以记录上各个数值的下标,加以判断。即下标不在需要的判断范围之内的就出来,不过这次是从队列头出列。因为去掉这些下标不合要求的数值之后,队列的头数值依然是最小值,故此是当前答案。


#include<cstdio>
const int MAX_N = 1000001;

int N, K;
int arr[MAX_N];
int qu[MAX_N];
int index[MAX_N];
int ans[MAX_N];

void getMins()
{
	int tail = 0, head = 1;	//初始化tail<head表示为空列
	for (int i = 1; i < K; i++)	//初始化单调队列
	{
		while (tail >= head && qu[tail] >= arr[i]) tail--;
		qu[++tail] = arr[i];		//记录可能的答案值
		index[tail] = i;	//记录额外需要判断的信息
	}
	for (int i = K; i <= N; i++)
	{
		while (tail >= head && qu[tail] >= arr[i]) tail--; //不符合条件出列
		qu[++tail] = arr[i];
		index[tail] = i;
		while (index[head] <= i-K) head++;
		ans[i-K] = qu[head];	//ans从下标0开始记录
	}
}

void getMaxs()
{
	int tail = 0, head = 1;
	for (int i = 1; i < K; i++)	//初始化单调队列
	{
		while (tail >= head && qu[tail] <= arr[i]) tail--;
		qu[++tail] = arr[i];
		index[tail] = i;
	}
	for (int i = K; i <= N; i++)
	{
		while (tail >= head && qu[tail] <= arr[i]) tail--; //不符合条件出列
		qu[++tail] = arr[i];
		index[tail] = i;
		while (index[head] <= i-K) head++;
		ans[i-K] = qu[head];	//ans从下标0开始记录
	}
}

int main()
{
	while (~scanf("%d %d", &N, &K))
	{
		for (int i = 1; i <= N; i++) scanf("%d", &arr[i]);
		getMins();
		for (int i = 0; i <= N-K; i++) printf("%d ", ans[i]);
		putchar('\n');
		getMaxs();
		for (int i = 0; i <= N-K; i++) printf("%d ", ans[i]);
		putchar('\n');
	}
	return 0;
}