单调队列

OI 知识>数据结构
777 words

单调队列

一，概览

单调队列的重点在于单调和队列

  1. 单调反映了元素变化的规律是递增或递减；
  2. 队列意味着对元素的操作只能在队头和队尾进行。

二，实现

建立一个队列，考虑要向里插入一个元素：

比较要插入的元素和现有的队尾，若满足所需的单调性，则直接插入队尾，若不满足单调性，则重复弹出队尾直到满足单调性或队列为空，之后将新元素插入队尾。

单调队列最经典的实现就是滑动窗口，即给出一个数组 \(a_{1,2,...,n}\)，给出一个长度 \(k\)，在数组中找到每一段长为 \(k\) 的区间的区间最值。

模板题面

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

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

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

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

样例输入 #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})\)。

deque 实现 
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
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005];
deque<int> q;
inline int rd()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void wt(int x)
{
    if(x<0) {putchar('-'),wt(-x);return;}
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),k=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    for(int i=1;i<=n;i++)
    {
        if(!q.empty()&&q.front()<i-k+1) q.pop_front();
        while(!q.empty()&&a[q.back()]>=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k) wt(a[q.front()]),putchar(' ');
    }
    putchar('\n'),q.clear();
    for(int i=1;i<=n;i++)
    {
        if(!q.empty()&&q.front()<i-k+1) q.pop_front();
        while(!q.empty()&&a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k) wt(a[q.front()]),putchar(' ');
    }
    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
#include<bits/stdc++.h>
using namespace std;
int n,k,a[1000005],q[1000005];
inline int rd()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline void wt(int x)
{
    if(x<0) {putchar('-'),wt(-x);return;}
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),k=rd();
    for(int i=1;i<=n;i++) a[i]=rd();
    int l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        if(l<=r&&q[l]<i-k+1) l++;
        while(l<=r&&a[q[r]]>=a[i]) r--;
        q[++r]=i;
        if(i>=k) wt(a[q[l]]),putchar(' ');
    }
    putchar('\n'),l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        if(l<=r&&q[l]<i-k+1) l++;
        while(l<=r&&a[q[r]]<=a[i]) r--;
        q[++r]=i;
        if(i>=k) wt(a[q[l]]),putchar(' ');
    }
    return 0;
}
Comments