滑动窗口

题目链接

转载自洛谷博客

此题为单调队列模板题。

单调队列有两个性质:

  1. 队列中的元素其对应在原来的列表中的顺序必须是单调递增的。

  2. 队列中元素的大小必须是单调递*(增/减/甚至是自定义也可以)

单调队列与普通队列不一样的地方就在于单调队列既可以从队首出队,也可以从队尾出队。

就拿样例来谈谈,设以最小的为标准:

1
2
8 3
1 3 -1 -3 5 3 6 7

下文中我们用q来表示单调队列,p来表示其所对应的在原列表里的序号。

  1. 由于此时队中没有一个元素,我们直接令1进队。此时,q={1},p={1}。

  2. 现在3面临着抉择。下面基于这样一个思想:假如把3放进去,如果后面2个数都比它大,那么3在其有生之年就有可能成为最小的。此时,q={1,3},p={1,2}

  3. 下面出现了-1。队尾元素3比-1大,那么意味着只要-1进队,那么3在其有生之年必定成为不了最小值,原因很明显:因为当下面3被框起来,那么-1也一定被框起来,所以3永远不能当最小值。所以,3从队尾出队。同理,1从队尾出队。最后-1进队,此时q={-1},p={3}

  4. 出现-3,同上面分析,-1>-3,-1从队尾出队,-3从队尾进队。q={-3},p={4}。

  5. 出现5,因为5>-3,同第二条分析,5在有生之年还是有希望的,所以5进队。此时,q={-3,5},p={4,5}

  6. 出现3。3先与队尾的5比较,3<5,按照第3条的分析,5从队尾出队。3再与-3比较,同第二条分析,3进队。此时,q={-3,3},p={4,6}

  7. 出现6。6与3比较,因为3<6,所以3不必出队。由于3以前元素都<3,所以不必再比较,6进队。因为-3此时已经在滑动窗口之外,所以-3从队首出队。此时,q={3,6},p={6,7}

  8. 出现7。队尾元素6小于7,7进队。此时,q={3,6,7},p={6,7,8}。

那么,我们对单调队列的基本操作已经分析完毕。因为单调队列中元素大小单调递*(增/减/自定义比较),因此,队首元素必定是最值。按题意输出即可。

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
#include<cstdio>
#include<cstring>
using namespace std;

struct Monotone_queue
{
static const int maxn=1000001;
int n,k,a[maxn];
int q[maxn],head,tail,p[maxn];//同题目叙述一样,q是单调队列,p是对应编号。

void read()
{
scanf("%d %d",&n,&k);
for(int i=1;i<=n;++i)
scanf("%d",&a[i]);
}//读入不必说了

void monotone_max()//单调最大值
{
head=1;
tail=0;
for(int i=1;i<=n;++i)
{
while(head<=tail&&q[tail]<=a[i])
tail--;
q[++tail]=a[i];
p[tail]=i;
while(p[head]<=i-k)
head++;
if(i>=k)printf("%d ",q[head]);
}
printf("\n");
}

void monotone_min()
{
head=1;
tail=0;//为啥要这样呢?因为head要严格对应首元素,tail要严格对应尾元素,所以当tail>=head时,说明有元素。而一开始队列为空,说一要这样赋值。其实这跟普通队列一样。
for(int i=1;i<=n;++i)
{//a[i]表示当前要处理的值
while(head<=tail&&q[tail]>=a[i])
tail--;//只要队列里有元素,并且尾元素比待处理值大,即表示尾元素已经不可能出场,所以出队。直到尾元素小于待处理值,满足"单调"。
q[++tail]=a[i];//待处理值入队。
p[tail]=i;//同时存下其编号
while(p[head]<=i-k)
head++;//如果队首元素已经"过时",出队。
if(i>=k)printf("%d ",q[head]);//输出最值,即队首元素。i>=k表示该输出,至于why就自己看题目。
}
printf("\n");

}
}worker;

int main()
{
worker.read();
worker.monotone_min();
worker.monotone_max();
return 0;
}

单调队列

用单调队列来解决问题,一般都是需要得到当前的某个范围内的最小值或最大值。

一篇详细的博客:传送门

例如:

Description
一个长度为n的整数序列,从中找出一段不超过m的连续子序列,使得整个序列的和最大。

例如: 1, -3, 5, 1, -2, 3

当m=4时,sum = 5+1-2+3 = 7

当m=2或m=3时,sum = 5+1 = 6

Input
多测试用例,每个测试用例:

第一行是两个正数n, m ( n, m ≤ 300000 )

第二行是n个整数

Output
每个测试用例输出一行:一个正整数,表示这n个数的最大子序和长度

Sample Input
6 4
1 -3 5 1 -2 3

Sample Output
7

这道题可以用dp来解,也可以用单调队列。

方法一:(第一反应的做法,当然没有完全按照题目的输出,主要是用于检验)

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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int a[300005];

int main(){
int n, m;
while(cin >> n >> m){
memset(a, 0, sizeof(a));
for(int i = 0; i < n; i++)
cin >> a[i];
int ans = 0, t = 0, temp = 0, len = 0, ans_l = 0, ans_t = 0;
while(t + len < n){
for(int i = t; i < t + m; i++){
temp += a[i];
len++;
if(ans < temp){
ans = temp;
ans_l = len;
ans_t = t;
}
}
t++;
len = 0; temp = 0;
}
cout << "start: " << ans_t << " " << "length: " << ans_l << endl;
cout << ans << endl;
}
return 0;
}

方法二:(单调队列)

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
//跟前缀和差不多
#include <iostream>
#include <algorithm>
#include <cstring>
#include <list>
using namespace std;

#define MIN -0x7fffffff
int sum[300005];
list <int> L;

int main(){
int n, m;
while(cin >> n >> m){
memset(sum, 0, sizeof(sum));
sum[0] = 0; //注意:这里一定要从sum[1]开始存储,并且设置sum[0] = 0,原因可以从下面的for循环和两个while循环推出
cin >> sum[1];
for(int i = 2; i <= n; i++){
cin >> sum[i];
sum[i] += sum[i - 1];
}
L.clear();
int ans = MIN;
L.push_front(0); //将下标i入队
for(int i = 1; i <= n; i++){
while(!L.empty() && i - L.back() > m){ //判断是否在范围(i-m,i)内,不在就pop
L.pop_back();
}
ans = max(ans, sum[i] - sum[L.back()]); //求最大值,sum[i]-sum[min],表示前i个中找到最小的来减,sum[min]就是单调队列的尾部sum[L.back()]
while(!L.empty() && sum[i] < sum[L.front()]){ //更新单调队列,比sum[i]大的值都去掉
L.pop_front();
}
L.push_front(i); //最后将下标i入队
}
cout << ans << endl;
}
return 0;
}

/*
Input:
9 5
3 7 -2 9 -9 6 5 -4 7
6 4
1 -3 5 1 -2 3
Output:
17
7
*/
You need to set client_id and slot_id to show this AD unit. Please set it in _config.yml.