what is it？
这是一个神奇的数据结构
我们从一道例题来看看单调队列的强大
例题1 滑动窗口
这是一类经典题型滑动窗口
区间找最值我们可能想到ST表RMQ这样的算法
但一般滑动窗口的题目n都特别大
而ST表要用到二维的数组，空间无法承受
单调队列闪亮登场
前备知识
我们可以用c++自带的STL双端队列deque来实现
当然也可以手动模拟
双端队列顾名思义可以在队列的两端操作(back,front)
与队列相似
q.push_back(x);//在队尾插入元素
q.push_front(x);//在队首插入元素
q.pop_back(x);//在队尾删除元素
q.pop_front(x);//在队首删除元素
从这道题来说我们只要管一个大小为k的区间内最值即可
我们可以用双端队列来实现单调队列
以求最小值为例
枚举每一个区间的右端点
在我们之前维护好的单调队列中做以下操作来维护
- 比较单调队列中的队尾元素与我们枚举到的i点数值大小
若i点数值小等于队尾我们直接把队尾弹出并重复这一步操作即可 - 将该点放入队尾
- 输出时比较队首在原数列中的位置是不是在i点前k个以内
不是弹出即可
for(int i=1;i<=n;i++){
while((!q1.empty())&&q1.back().data>=a[i])
q1.pop_back();
node u;
u.id=i;u.data=a[i];
q1.push_back(u);
while(q1.front().id+k-1<i)
q1.pop_front();
if(i>=k)
printf("%d ",q1.front().data);
}
第1步的理由:
在队列中先入队的编号一定比i小，若数值还比a[i]大
那最小值一定不是它，并且之后的位置它也会比i先出队
简单来说
有些巨佬比你小还比你强，你怎么赢ta？
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005;
struct node{
int id,data;
};
int n,k;
int a[maxn];
deque<node>q1,q2;
void work(){
for(int i=1;i<=n;i++){
while((!q1.empty())&&q1.back().data>=a[i])
q1.pop_back();
node u;
u.id=i;u.data=a[i];
q1.push_back(u);
while(q1.front().id+k-1<i)
q1.pop_front();
if(i>=k)
printf("%d ",q1.front().data);
}
printf("\n");
for(int i=1;i<=n;i++){
while((!q2.empty())&&q2.back().data<=a[i])
q2.pop_back();
node u;
u.id=i;u.data=a[i];
q2.push_back(u);
while(q2.front().id+k-1<i)
q2.pop_front();
if(i>=k)
printf("%d ",q2.front().data);
}
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
work();
return 0;
}
从这里我们应该可以看出为什么叫单调队列了
它不仅维护了data的单调性还维护了编号的单调性
练习1 求m区间内的最小值
注意此题为左闭右开区间
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000005;
struct node{
int id,data;
};
int a[maxn];
deque<node>q;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=m;i++){
if(q.empty())printf("0\n");
else printf("%d\n",q.front().data);
while((!q.empty())&&q.back().data>=a[i])
q.pop_back();
node u;
u.id=i;u.data=a[i];
q.push_back(u);
}
//特殊考虑前m个
for(int i=m+1;i<=n;i++){
printf("%d\n",q.front().data);
while((!q.empty())&&q.back().data>=a[i])
q.pop_back();
node u;
u.id=i;u.data=a[i];
q.push_back(u);
while(q.front().id+m-1<i)
q.pop_front();
}
return 0;
}
例题2 切蛋糕
这道题没有固定的区间长度，只有最多m块的限制
由于我们要求的是区间最大和
我们可以考虑前缀和
将前缀和放到单调队列中维护最小值
同样是枚举区间右端点减去单调队列维护的最小前缀和就能得到区间最大和了
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
struct node{
int id,data;
};
int c[maxn];
deque<node>q;
int ans=0;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
c[i]=c[i-1]+x;
}
for(int i=1;i<=n;i++){
while((!q.empty())&&q.back().data>=c[i])
q.pop_back();
node u;
u.id=i;u.data=c[i];
q.push_back(u);
while(q.front().id+m-1<i)
q.pop_front();
ans=max(ans,c[i]-q.front().data);
}
printf("%d",ans);
return 0;
}
例题3 良好的感觉
这道题的区间范围更加混乱了，整个在放飞自我
由于我们这个区间的舒适程度只与区间内最小元素和元素和有关
而区间元素越多区间元素和可能更优
那我们以每个点为所在区间的最小值找到这个最大区间不就解决问题了吗
怎么快速找到以i点值为最小值的最大区间呢
自然是在两边找到了比i值更小的值，这个区间就无法更大了
注意 我们要维护的比i值更小的值是从i ~ 1和从i ~ n第一个比i小的
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
struct node{
int id,data;
};
int x[maxn];
long long c[maxn];
int l[maxn],r[maxn];
long long ans=0;
deque<node>q;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&x[i]);
c[i]=c[i-1]+x[i];
}
for(int i=1;i<=n;i++){
while((!q.empty())&&q.back().data>=x[i])
q.pop_back();
if(q.empty())l[i]=0;
else l[i]=q.back().id;//利用了单调队列编号的单调性
//这个队尾的值没被弹掉说明它比x[i]小，且在x[i]之前入队
node u;
u.id=i;u.data=x[i];
q.push_back(u);
}
q.clear();
for(int i=n;i>=1;i--){
while((!q.empty())&&q.back().data>=x[i])
q.pop_back();
if(q.empty())r[i]=n+1;
else r[i]=q.back().id;
//同上
node u;
u.id=i;u.data=x[i];
q.push_back(u);
}
for(int i=1;i<=n;i++)
ans=max(ans,(c[r[i]-1]-c[l[i]])*x[i]);
printf("%lld",ans);
return 0;
}
练习2 [SCOI2009]生日礼物
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000005,maxk=65,inf=0x3f3f3f3f;
struct node{
int id,data;
bool operator <(node i)const{
return id<i.id;
}
}a[maxn];
int len=0,cnt=0;
int ans=inf;
int pos[maxk];
deque<node>q;
int main()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i=1;i<=k;i++){
int t;
scanf("%d",&t);
for(int j=1;j<=t;j++){
int x;
scanf("%d",&x);
++len;
a[len].id=x;a[len].data=i;
}
}
sort(a+1,a+len+1);
for(int i=1;i<=len;i++){
if(!pos[a[i].data])cnt++;
pos[a[i].data]=a[i].id;
q.push_back(a[i]);
while((!q.empty())&&q.front().id!=pos[q.front().data])
q.pop_front();
if(cnt==k)ans=min(ans,a[i].id-q.front().id);
}
printf("%d",ans);
return 0;
}
