(luogu1886)滑动窗口

发表于 | 分类于 ，

一道单调队列的入门题

题目描述:

给出一个有n(n<=1e6)个数字的序列, 以及一个大小为k(k<=n)的窗口, 这个窗口从最左边开始往右滑动, 每次滑动一个单位, 求这个序列里在这个窗口中的数的最大和最小值

思路:

单调队列的入门题

维护两个单调队列, 一个递增, 一个递减, 分别表示最大值和最小值, 移动窗口前时判断队首是否等于当前最左端值, 如果相等则队首出队

代码:

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
#include <iostream>
#include <cstdio>
using namespace std;
const int Mn(1000005);
struct sq
{
    private:
        const static int MS=1000005;
        int q[Mn];
        bool isu;
        int h,t,s; //队首, 队尾及队的大小
    public:
        sq(bool b=true):h(0),t(0),s(0),isu(b) {} //false表递减, true表递增
        bool emp()
		{ return !s; }
        int fr()
		{ return q[h]; }
        void pop()
		{ if(s) h=(h+1)%MS,--s; } //单调队列出队操作
        void push(int x)
		{
            if(isu)
            {
                while(s && q[(t-1+MS)%MS]<x) //当队尾小于当前插入值时, 队尾出队
                {
                    t=(t-1+MS)%MS;
                    --s;
                }
                q[t] = x, t=(t+1)%MS, ++s;
            }
            else
            {
                while(s && q[(t-1+MS)%MS]>x) //递减相反
                {
                    t=(t-1+MS)%MS;
                    --s;
                }
                q[t] = x, t=(t+1)%MS, ++s;
            }
        }
};
int a[Mn];
int main()
{
    int n,k;
    cin >> n >> k;
    for(int i(1);i<=n;++i)
        scanf("%d",a+i);
    sq mn(false),mx(true);
    for(int i(1);i<=k;++i)
        mn.push(a[i]),mx.push(a[i]);
    cout << mn.fr();
    for(int i(2);i+k-1<=n;++i)
    {
        if(a[i-1]==mn.fr())	mn.pop(); //判定队首是否在窗口中
        mn.push(a[i+k-1]); //窗口右端入队
        cout << " " << mn.fr();
    }
    cout << endl << mx.fr();
    for(int i(2);i+k-1<=n;++i) //同上
    {
        if(a[i-1]==mx.fr())	mx.pop();
        mx.push(a[i+k-1]);
        cout << " " << mx.fr();
    }
    return 0;
}