0%

5.11创新班总结

今天的创新班,学的就是单调队列。

题目:给定一个长度为N的数列,求出每一个区间长度为K的最大值。

样例输入:

8,7,12,5,4,2,16,9,17,8

样例输出:

12,12,12,5,16,16,17,17

传统做法:我们首先想到的就是硬枚举。从第1位枚举到第N-K+1位,再枚举区间K的每一位,得到最大值。但是,时间复杂度为O(N*K),若数据再大一点,就无法AC了。那怎么办呢?我们发现,比较[8,7,12]与[7,12,5]时,[7,12]就重复了,而且,答案也是12。

思想:单调队列是指一个队列中的数单调递增(或者递减),是一个方便求指定区间极值的一种队列。简单来说,首先我们求得第一个区间的最大值是[12],然而,这就说明了再以后的区间中,另外两个数[8,7]再也不可能成为最大值,因为比它大的数[12]在[8,7]后面。

维护队列:

对于样例,我们来模拟一下:

i=1:插入8,队列为:(8) {i=1<3,不输出队首8}

i=2:插入7,队列为:(8,7) {i=2<3,不输出队首8}

i=3:插入12,队列为:(12,8,7){12大于7和8,依次删除队尾的7和8,并插入12到队列,且i=3了,故输出队首的12}

i=4:插入5,队列为:(12,5) {i≥3,输出队首12}

i=5:插入4,队列为:(12,5,4) {i≥3,输出队首12}

i=6:插入2,队列为:(12,5,4,2){i≥3,2插入后,因为队列中的元素多于了3个,队首的12没用了故被删除,输出此时的队首5,}

i=7:插入16,队列为:(16 5,4,2) {16大于队尾的2、4、5,依次删除2、4、5,并输出队首16}

i=8:插入9,队列为:(16,9) {i≥3,输出队首16}

i=9:插入17,队列为:(17 16,9) {i≥3,输出队首17}

i=10:插入8,队列为(17,8) {i≥3,输出队首17}

程序:

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <fstream>
using namespace std;

ifstream fin("dandiao.in");
ofstream fout("dandiao.out");

struct data
{
int x,p;
};

int n,k;
data b1[100002],b2[100002];
int h1=1,t1=1,h2=1,t2=1,a[100002],ans=999999;

void read();
void insert1(int x,int p);
void insert2(int x,int p);
void work();

int main()
{
read();

work();

return 0;
}

void read()
{
fin >>n >>k;
for (int i=1;i<=n;++i) fin >>a[i];
}

void insert1(int x,int p)
{
int i=t1;
for (;i>=h1 && x>b1[i].x;--i);
i++;
b1[i].x=x;
b1[i].p=p;
t1=i;
}

void insert2(int x,int p)
{
int i=t2;
for (;i>=h2 && x<b2[i].x;--i);
i++;
b2[i].x=x;
b2[i].p=p;
t2=i;
}

void work()
{
b1[1].x=a[1];
b1[1].p=1;
b2[1].x=a[1];
b2[1].p=1;

for (int i=2;i<=n;++i)
{
if (i-k+1>b1[h1].p) h1++;
insert1(a[i],i);
if (i-k+1>b2[h2].p) h2++;
insert2(a[i],i);
if (ans>(b1[h1].x-b2[h2].x) && i>=k)
ans= b1[h1].x-b2[h2].x;
}

fout <<ans <<endl;
}
Thank you so much.