5单调队列学习笔记
【5】单调队列学习笔记
前言
鸽了很久，
2023 / 1 / 5 2023/1/5
2023/1/5 开始，
2023 / 1 / 21 2023/1/21
2023/1/21 才完工。
中途去集训了，没时间来补漏洞。
单调队列
单调队列是一种非常实用的数据结构，可以用于查询一个 定长区间 在以一定速度向后 滑动 ，并查询 区间内最值 的问题（具体见例题
1 1
1 ）。时间复杂度非常低，总体是
O ( n ) O(n)
O
(
n
) ，均摊到每个元素是
O ( 1 ) O(1)
O
(
1
) ，所以常用来优化其他算法。
单调队列需要保证队列元素的 单调性 ，也就是说，要保证 队头就是最值 ，这样就可以做到
O ( 1 ) O(1)
O
(
1
) 查询最值。
单调队列的维护：
1 1
1 ：向后滑动的过程中，会有新的元素加入队列。这时候，为了保证队列单调性，就应该把新元素与队尾元素 比较大小 。如果比队尾元素更接近最值，那么表示这个元素既比队尾元素 优 ，又比队尾元素的 时间晚 ，队尾元素会在这个元素之前被移出区间。这时存储这个元素就没有必要，可以直接 前移队尾指针 ，把队尾元素移除队列。重复执行直到 队列为空 或 该元素不比队尾元素优 ，最后该元素入队。
2 2
2 ：向后滑动的过程中，会有旧的元素退出队列。可以记录每个元素的 入队位置 ，根据 现在的位置 和 队列长度 计算出队首元素是否退出队列。如果退出，可以后移队头指针，将队首元素 出队 。重复执行直到队首元素满足要求。
具体代码详见各题目。
单调队列例题
例题
1 1
1 ：
单调队列模板题，不多赘述。
此处用的是
for
循环，代码比较冗余，简洁的模板请见其他题目。
#include <bits/stdc++.h>
using namespace std;
int n,k,a[2000050],heads=0,tails=0,headb=0,tailb=0;
struct node
{
int v,t;
}stb[2000050],sts[2000050];
inline int read()
{
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-48;ch=getchar();}
return x*f;
}
int main()
{
n=read();k=read();
for(int i=1;i<=n;i++)
a[i]=read();
sts[++heads].t=1;sts[heads].v=a[1];tails++;
if(k==1)printf("%d ",sts[heads].v);
for(int i=2;i<=n;i++)
{
for(int j=tails;a[i]<sts[j].v&&j>=heads;j--)tails--;
sts[++tails].t=i;sts[tails].v=a[i];
for(int j=heads;j<=tails&&i-sts[j].t>=k;j++)heads++;
if(i>=k)printf("%d ",sts[heads].v);
}
printf("\n");
stb[++headb].t=1;stb[headb].v=a[1];tailb++;
if(k==1)printf("%d ",stb[headb].v);
for(int i=2;i<=n;i++)
{
for(int j=tailb;a[i]>stb[j].v&&j>=headb;j--)tailb--;
stb[++tailb].t=i;stb[tailb].v=a[i];
for(int j=headb;j<=tailb&&i-stb[j].t>=k;j++)headb++;
if(i>=k)printf("%d ",stb[headb].v);
}
return 0;
}例题
2 2
2 ：
如果一头奶牛
D D
D 范围内的最高奶牛都不是它的两倍，那么这头奶牛就不会拥挤。所以可以通过查询最大值来确定是否会拥挤，就转化为了滑窗最大值问题。
首先把奶牛按照
x i x_i
x
i
升序排列，然后以
x i x_i
x
i
为位置，
h i h_i
h
i
为值建立单调队列查询最大值，队列长度为
D D
D 。单调队列需要正着跑一遍，反着跑一遍，求出两边的最大值。
注意这里是先计算，再插入值。因为奶牛自己不会拥挤自己。
当然不这样也可以，因为奶牛自己的身高不会是自己的
2 2
2 倍以上。
#include<bits/stdc++.h>
using namespace std;
struct cow
{
long long h,x;
}c[300000],que[300000];
long long n,d,cnt=0;
bool book1[300000],book2[300000];
bool cmp(struct cow a,struct cow b)
{
return a.x<b.x;
}
int main()
{
scanf("%lld%lld",&n,&d);
for(long long i=0;i<n;i++)scanf("%lld%lld",&c[i].x,&c[i].h);
sort(c,c+n,cmp);
long long head=0,tail=0;
que[++tail]=c[0];
head++;
for(long long i=1;i<n;i++)
{
while(que[head].x<c[i].x-d&&head<=tail)head++;
if(que[head].h>=c[i].h*2)book1[i]=1;
while(que[tail].h<=c[i].h&&tail>=head)tail--;
que[++tail]=c[i];
}
head=0;tail=0;
que[++tail]=c[n-1];
head++;
for(long long i=n-2;i>=0;i--)
{
while(que[head].x>c[i].x+d&&head<=tail)head++;
if(que[head].h>=c[i].h*2)book2[i]=1;
while(que[tail].h<=c[i].h&&tail>=head)tail--;
que[++tail]=c[i];
}
for(long long i=0;i<n;i++)
if(book1[i]&&book2[i])cnt++;
printf("%lld\n",cnt);
return 0;
}例题
3 3
3 ：
答案是满足单调性的。越宽的花盆，可以得到的答案就越大。反之亦然。所以可以通过二分答案来做。
验证答案时，由于需要查询最值，而花盆长度固定，可以假设花盆从左向右滑动，最后的答案是每次滑动后最大值与最小值的差的最大值，实际上就是枚举花盆的结束点。所以就转化为了滑窗最值问题，可以跑两遍单调队列。一遍跑最大值，一遍跑最小值。
把奶牛按照
x i x_i
x
i
升序排列，然后以
x i x_i
x
i
为位置，
y i y_i
y
i
为值建立单调队列查询最大值和最小值，队列长度为二分查找时的
m i d mid
mi
d 。最后把每次滑动后最大值与最小值的差的最大值与
D D
D 比较，就能知道答案的正确性了。
注意，如果一个答案合理，那么还可以尝试更小的花盆，不能直接退出。
听说ST表也能做，但是效率绝对没有单调队列高。
#include <bits/stdc++.h>
using namespace std;
struct drop
{
int x,y;
}water[100010],que[300010];
int n,d,l=1,r=99999999,ans=-1,h=0,t=0;
int maxn[1000100],minn[1000100];
bool cmp1(struct drop a,struct drop b)
{
return a.x<b.x;
}
bool check(int l)
{
int ans=0;
memset(maxn,0,sizeof(maxn));
memset(minn,0,sizeof(minn));
h=0;t=0;
que[++h].x=water[0].y;que[++t].y=water[0].x;
maxn[0]=water[0].y;
for(int i=1;i<n;i++)
{
while(que[t].x<=water[i].y&&h<=t)t--;
que[++t].x=water[i].y;que[t].y=water[i].x;
while(water[i].x-que[h].y>l&&h<=t)h++;
maxn[i]=que[h].x;
}
h=0;t=0;
que[++h].x=water[0].y;que[++t].y=water[0].x;
minn[0]=water[0].y;
for(int i=1;i<n;i++)
{
while(que[t].x>=water[i].y&&h<=t)t--;
que[++t].x=water[i].y;que[t].y=water[i].x;
while(water[i].x-que[h].y>l&&h<=t)h++;
minn[i]=que[h].x;
}
for(int i=0;i<n;i++)
ans=max(ans,maxn[i]-minn[i]);
return ans>=d;
}
int main()
{
scanf("%d%d",&n,&d);
for(int i=0;i<n;i++)
scanf("%d%d",&water[i].x,&water[i].y);
sort(water,water+n,cmp1);
while(l<r)
{
int mid=(l+r)/2;
if(check(mid))ans=mid,r=mid;
else l=mid+1;
}
printf("%d",ans);
return 0;
}单调队列的运用
单调队列是可以用来优化DP的，可以把一部分
O ( n 2 ) O(n^2)
O
(
n
2
) 的DP优化到
O ( n ) O(n)
O
(
n
) ，是一个非常大的优化。
当然，想使用单调队列优化DP，还是需要一定的想象力的。
例题
4 4
4 ：
很容易写出这样一个转移方程：
d p [ i ]
max { d p [ i − j ] } + a [ i ] ( L ≤ j ≤ R ) dp[i]=\max{dp[i-j]}+a[i](L\le j\le R)
d
p
[
i
]
=
max
{
d
p
[
i
−
j
]}
a
[
i
]
(
L
≤
j
≤
R
)
如果这样子朴素转移，时间复杂度是
O ( n ( L − R ) ) O(n(L-R))
O
(
n
(
L
−
R
)) 的，很容易超时。
我们观察到，
j j
j 的取值范围
( L ≤ j ≤ R ) (L\le j\le R)
(
L
≤
j
≤
R
) 是不变的，也就意味着可以取的
d p [ i − j ] dp[i-j]
d
p
[
i
−
j
] 的个数是不变的。又因为
j j
j 在取值范围
( L ≤ j ≤ R ) (L\le j\le R)
(
L
≤
j
≤
R
) 中是连续自然数，所以
d p [ i − j ] dp[i-j]
d
p
[
i
−
j
] 是连续的。
d p [ i − j ] dp[i-j]
d
p
[
i
−
j
] 的取值就像一个固定长度的窗口。
d p [ i − j ] dp[i-j]
d
p
[
i
−
j
] 中，我们需要逐个递增枚举
i i
i 。那么此时
d p [ i − j ] dp[i-j]
d
p
[
i
−
j
] 的取值也会随之逐个递增，就像一个固定长度的滑动窗口。就像这样：
对这是滑动窗口的原图
而此时需要求的就是
d p [ i − j ] dp[i-j]
d
p
[
i
−
j
] 的取值中的最大值，可以使用单调队列来维护。
注意如果
i < L i\lt L
i
<
L ，证明无法跳到这个格子，可以赋值为负无穷，排除干扰。
#include <bits/stdc++.h>
using namespace std;
int n,l,r,a[2000050],f[2000050],head=0,tail=0,ans=-99999999;
struct node
{
int t,v;
}que[2000050];
inline int read()
{
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-48;ch=getchar();}
return x*f;
}
int main()
{
n=read();l=read();r=read();
for(int i=1;i<=n+1;i++)
a[i]=read();
que[++tail].t=1;que[tail].v=a[1];head++;
f[1]=a[1];
for(int i=2;i<=n+r+1;i++)
{
f[i]=-99999999;
if(i>l)
{
while(que[tail].v<=f[i-l]&&tail>=head)tail--;
que[++tail].t=i-l;que[tail].v=f[i-l];
while(que[head].t<i-r&&head<=tail)head++;
f[i]=que[head].v+a[i];
}
}
for(int i=n+1;i<=n+r+1;i++)
ans=max(ans,f[i]);
printf("%d",ans);
return 0;
}例题
5 5
5 ：
双倍经验
正着DP不好想，不如正难则反，要使选出的数字的和最大，就是要不选的数字和最小。
很容易写出这样一个逆向DP的转移方程：
d p [ i ]
min { d p [ i − j ] } + a [ i ] ( 0 < j ≤ k ) dp[i]=\min{dp[i-j]}+a[i](0\lt j\le k)
d
p
[
i
]
=
min
{
d
p
[
i
−
j
]}
a
[
i
]
(
0
<
j
≤
k
)
依据例题
4 4
4 的分析，这个式子也可以用单调队列来维护
min { d p [ i − j ] } \min{dp[i-j]}
min
{
d
p
[
i
−
j
]} ，把时间复杂度降为
O ( n ) O(n)
O
(
n
) 。
P2034
#include <bits/stdc++.h>
using namespace std;
long long n,k,a[2000050],f[2000050],head=0,tail=0,ans=99999999999999,tol=0;
struct node
{
long long t,v;
}que[2000050];
inline long long read()
{
long long 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-48;ch=getchar();}
return x*f;
}
int main()
{
n=read();k=read();
for(long long i=0;i<n;i++)
{
a[i]=read();
tol+=a[i];
}
que[++tail].t=0;que[tail].v=a[0];head++;
f[0]=a[0];
for(long long i=1;i<n;i++)
{
if(i-k-1>=0)
{
while(que[head].t<i-k-1&&head<=tail)head++;
f[i]=que[head].v;
}
f[i]+=a[i];
while(que[tail].v>f[i]&&head<=tail)tail--;
que[++tail].v=f[i];que[tail].t=i;
}
for(long long i=n-k-1;i<n;i++)
ans=min(f[i],ans);
printf("%lld",tol-ans);
return 0;
}P2627
#include <bits/stdc++.h>
using namespace std;
long long n,k,a[2000050],f[2000050],head=0,tail=0,ans=99999999999999,tol=0;
struct node
{
long long t,v;
}que[2000050];
inline long long read()
{
long long 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-48;ch=getchar();}
return x*f;
}
int main()
{
n=read();k=read();
for(long long i=0;i<n;i++)
{
a[i]=read();
tol+=a[i];
}
que[++tail].t=0;que[tail].v=a[0];head++;
f[0]=a[0];
for(long long i=1;i<n;i++)
{
if(i-k-1>=0)
{
while(que[head].t<i-k-1&&head<=tail)head++;
f[i]=que[head].v;
}
f[i]+=a[i];
while(que[tail].v>f[i]&&head<=tail)tail--;
que[++tail].v=f[i];que[tail].t=i;
}
for(long long i=n-k-1;i<n;i++)
ans=min(f[i],ans);
printf("%lld",tol-ans);
return 0;
}后记
单调队列还是很需要想象力的，否则没有那么好理解。
顺便纪念一下，这是我农历虎年的最后一篇博客！