地址：P1886

滑动窗口 /【模板】单调队列

题目描述

有一个长为 $n$ 的序列 $a$，以及一个大小为 $k$ 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

例如，对于序列 $[1,3,-1,-3,5,3,6,7]$ 以及 $k = 3$，有如下过程：

输入格式

输入一共有两行，第一行有两个正整数 $n,k$。
第二行 $n$ 个整数，表示序列 $a$

输出格式

输出共两行，第一行为每次窗口滑动的最小值
第二行为每次窗口滑动的最大值

样例 #1

样例输入 #1

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

样例输出 #1

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

提示

【数据范围】
对于 $50\%$ 的数据，$1 \le n \le 10^5$；
对于 $100\%$ 的数据，$1\le k \le n \le 10^6$，$a_i \in [-2^{31},2^{31})$。

根据题目来看，本题是单调队列（窗口）模版题，所以主要思路是看如何用单调队列来做。

什么是单调队列

在一个序列中，如果里面的值的单调的，那么便可以成为单调队列。

本题思路

以样例来举例最小值情况

开始队列中没有数，于是加入数字“1”
之后第二个数加入，因为“3”是大于“1”的，所以“1”是有可能成为整个窗口中的最小值的
接下来“-1”加入，这个时候就要注意了，我们的窗口是滑动的，而“-1”在“1、3”的后面，所以1和3这辈子不可能成为最小的数了，那么在我们的队列中，我们可以直接把1和3剔除，那么我们现在的队列中就只剩下了“-1”。
同时我们还需要一个记录编号的值，去记录队列里元素的数量，如果一直没有剔除元素，那么就当队列满时，去掉最前面的元素就可以了。
继续向下，因为“-3”小于“-1”，所以-1也可以剔除
“5”大于“-3”，所以队列变为“-3,5”
“3”小于5大于-3，所以队列变为“-3,3”
“6”大于前面的数，所以保留，但是因为这个时候发现“-3”的编号超过了队列的长度，所以剔除“-3”，队列变为“3,6”
最后“7”大于前面的数，队列最终为“3,6,7”
那么每一步的最小值就分别是“-1 -3 -3 -3 3 3”
最大值同理
下面是代码

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
#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;
}