单调队列 板子 洛谷 滑动窗口_洛谷华东窗口

单调队列并不难理解，说白了就是个队列，只不过这个队列可以两头出维护一个范围的单调性。但是，要实现这串代码还真挺巧妙的。
洛谷 p1886 滑动窗口

以下是引用洛谷的代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f;
int n,m;
int q1[1000001],q2[1000001];
int a[1000001];
int min_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        if(h<=t&&q1[h]+m<=i)
            h++;
        while(h<=t&&a[i]<a[q1[t]])
            t--;
        q1[++t]=i;
        if(i>=m)
            printf("%d ",a[q1[h]]);
    }
    cout<<endl;
}
int max_deque()
{
    int h=1,t=0;
    for(int i=1;i<=n;i++)
    {
        if(h<=t&&q2[h]+m<=i) h++;
        while(h<=t&&a[i]>a[q2[t]]) t--;
        q2[++t]=i;
        if(i>=m) printf("%d ",a[q2[h]]);
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    min_deque();
    max_deque();
    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