poj 2823 Sliding Window 单调队列

缘起

学习新的数据结构——单调队列啦~ poj 2823 Sliding Window

分析

这是单调队列的板题.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
就是给你一个长度为n的整数序列(n<=100w), 然后给你一个k
k是滑动窗口的长度. 然后要你输出窗口从左往右的最大值和最小值

【输入】
两行，第一行是n和k, 第二行是n个整数

【输出】
两行，第一行是窗口的最小值序列，第二行是查看的最大值序列

【样例输入】
8 3
1 3 -1 -3 5 3 6 7

【样例输出】
-1 -3 -3 -3 3 3
3 3 5 5 6 7

【限制】
12s

本题的n给的很到位——100w, 如果你使用朴（bao）素（li）的O(n^2)算法的话，负责任的说，你算到明天，估计也算不出来. 所以引入了一种叫单调队列的数据结构来高效的维护这种窗口极值问题.

单调队列，顾名思义——就是队列中的元素是单调的. 以本题求窗口最大值为例. 只需要维护一个单调队列. 里面的元素从队首到队尾是单调下降的. 保存了距离当前索引i距离<=k的最大的几个元素. 队首元素显然就是窗口极值. 但是还需要O(1)时间知道队首是否过期了（即已经不在窗口中了）?所以队列中要维护的是元素在数组中的索引而不是值. 一旦队首过期，则就要将其出队.

最后多说一句——还是自己用数组实现队列比较好. 用STL 的 dequeue（双端队列）比较慢.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//#include "stdafx.h"

#include <stdio.h>
//#define LOCAL

const int maxn = 1000005;
int n,k,a[maxn], q[maxn], front, rear; // ma是存储窗口极大值的, mi是存储窗口极小值

void get_min() // 窗口极小
{
	front = rear = 0; // 清空队列, 队列的范围是[front, rear)
	for (int i =1;i<=n;i++) // 顺次读入
	{
		while(front!=rear&&a[q[rear-1]]>a[i]) rear--; // 窗口极小中, 单调队列从队首到队尾是单调上升的
		q[rear++] = i; // 进队
		if (i>=k) // 如果已经诞生了一个完整的窗口了, 就要打印了
		{
			printf("%d", a[q[front]]);
			if (i<n) putchar(' ');
		}
		if (i-q[front]+1>=k) front++; // O(1)时间维护队列（即看看队首是不是过期了）, 所以队列中存储的应该是数组索引而不是值,这句代码是判断队列中是否已经有k个元素了,则队首肯定要出队了
	}
	puts("");
}

void get_max() // 窗口极大
{
	front = rear = 0;
	for (int i = 1; i<=n;i++)
	{
		while(front!=rear && a[q[rear-1]]<a[i]) rear--;
		q[rear++] = i;
		if (i>=k)
		{
			printf("%d",a[q[front]]);
			if (i<n) putchar(' ');
		}
		if (i-q[front]+1>=k) front++;
	}
	puts("");
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &k);
	for (int i = 1; i<=n;i++) scanf("%d", a+i);
	get_min();
	get_max();
	return 0;
}

ac情况

Status Accepted
Time 5907ms
Memory 4012kB
Length 1061
Lang C++
Submitted 2019-08-28 17:45:36
Shared
RemoteRunId 20812675