单调队列（2019.5.25训练）
本次训练共7题，本文附AC代码和题目链接。
先介绍C++的STL中双端队列的使用方法。
定义双端队列deque<int>q;
双端队列对队首和队尾都可以进行操作，具体如下：
q.push_front(x);//x入队首
q.push_back(x);//x入队尾
q.pop_front();//删除队首元素
q.pop_back();//删除队尾元素
洛谷 P1440 求m区间内的最小值
维护一个单调递增的双端队列，用ans数组记录队首元素，ans[i]表示a[i]及其之前的m-1个元素***m个元素)的最小值，所以最后输出ans[0]~ans[n-1]即可。
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,a[N],ans[N];
deque<int>q;//定义双端队列q，用来存放下标i
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
while(!q.empty()&&i-q.front()>=m)//若队首元素与现在遍历的元素下标之差大于等于m，则删除队首元素
q.pop_front();
while(!q.empty()&&a[q.back()]>a[i])//若队尾元素大于现在遍历的元素，说明现在出现了比之前小的值，则删除队尾元素
q.pop_back();
q.push_back(i);
ans[i]=a[q.front()];
}
for(int i=0;i<=n-1;i++)
printf("%d\n",ans[i]);
return 0;
}
洛谷 P2032 扫描
维护一个单调递减队列，也就是维护[i-m+1,i]区间内a[i]的最大值(即队列队首元素)。
#include <bits/stdc++.h>
const int N=2e6+10;
using namespace std;
int n,m,a[N],ans[N];
deque<int>q;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
while(!q.empty()&&i-q.front()>=m)
q.pop_front();
while(!q.empty()&&a[q.back()]<a[i])
q.pop_back();
q.push_back(i);
ans[i]=a[q.front()];
}
for(int i=m;i<=n;i++)
printf("%d\n",ans[i]);
return 0;
}
洛谷 P1886 滑动窗口
维护两个单调队列，一个递增，一个递减，开两个数组分别记录两个队列的队首元素，最后注意从下标m开始输出答案。
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N],mi[N],mx[N];
deque<int>q1,q2;//q1为递增队列，q2为递减队列
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
{
while(!q1.empty()&&i-q1.front()>=m)
q1.pop_front();
while(!q1.empty()&&a[q1.back()]>a[i])
q1.pop_back();
q1.push_back(i);
while(!q2.empty()&&i-q2.front()>=m)
q2.pop_front();
while(!q2.empty()&&a[q2.back()]<a[i])
q2.pop_back();
q2.push_back(i);
mi[i]=a[q1.front()];
mx[i]=a[q2.front()];
}
for(int i=m;i<=n;i++)
i==n?printf("%d\n",mi[i]):printf("%d ",mi[i]);
for(int i=m;i<=n;i++)
i==n?printf("%d\n",mx[i]):printf("%d ",mx[i]);
return 0;
}
洛谷 P1714 切蛋糕
用前缀和预处理，用单调队列维护[i-m,i]区间内前缀和的最小值，
(实际上求和区间是[i-m+1,i]，但是这个区间内的和用sum数组表示为sum[i]-sum[i-m]，即把sum的区间看成[i-m,i])
则每次遍历的区间内所有元素和的最大值为sum[i]-sum[q.front()]，找出sum[i]-sum[q.front()]的最大值即可。
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,x,mx,sum[N];
deque<int>q;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>x;
sum[i]=sum[i-1]+x;
}
for(int i=1;i<=n;i++)
{
while(!q.empty()&&i-q.front()>m)//没有等于号
q.pop_front();
while(!q.empty()&&sum[q.back()]>sum[i])
q.pop_back();
q.push_back(i);
mx=max(mx,sum[i]-sum[q.front()]);
}
printf("%d\n",mx);
return 0;
}
洛谷 P2629 好消息，坏消息
断环为链，把a[1]~a[n-1]接在a[n]之后，形成一个长度为2*n-1的序列，滑动窗口长度为n。
前缀和预处理，用单调队列维护前缀和的最小值，[i-m,i]区间内sum最小值为sum[q.front()]，只要保证该区间内和的最小值sum[q.front()]-sum[i-n]>=0，则可以保证在[i-m+1,i]区间内所有元素和或者部分元素和都大于等于0。
#include <bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,ans,a[N],sum[N];
deque<int>q;
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=n+1;i<=2*n-1;i++)
{
a[i]=a[i-n];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=2*n-1;i++)
{
while(!q.empty()&&i-q.front()>n)//没有等于号
q.pop_front();
while(!q.empty()&&sum[q.back()]>sum[i])
q.pop_back();
q.push_back(i);
if(i>=n&&sum[q.front()]-sum[i-n]>=0)ans++;
}
printf("%d\n",ans);
return 0;
}
洛谷 P1725 琪露诺
单调队列优化DP。
用dp[i]表示到达i位置时的和，滑动窗口长度为m=r-l+1，用单调队列维护dp值的滑动窗口，最后在[n-m+1,n]区间内找到dp最大值即为答案。注释详见代码。
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10,inf=0x3f3f3f3f;
int n,m,l,r,mx,a[N],dp[N];
deque<int>q;
int main()
{
ios::sync_with_stdio(false);
cin>>n>>l>>r;
m=r-l+1;//m为滑动窗口大小
for(int i=0;i<=n;i++)
cin>>a[i];
memset(dp,-inf,sizeof(dp));//注意dp初始化为最小值
dp[0]=0;
for(int i=0;i<=n-l;i++)
{
if(i-q.front()>=m)
q.pop_front();
while(!q.empty()&&dp[q.back()]<dp[i])//维护一个递减队列，队首为[i-m+1,i]区间内dp的最大值
q.pop_back();
q.push_back(i);
dp[i+l]=dp[q.front()]+a[i+l];//dp[i+l]表示跳到i+l位置时的最大和
}
mx=-inf;
for(int i=n-m+1;i<=n;i++)
mx=max(mx,dp[i]);
printf("%d\n",mx);
return 0;
}
洛谷 P2422 良好的感觉
洛谷数据很水，写了个O(n2)的暴力竟然也能AC…
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll n,l,r,mx,a[N],sum[N];
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
l=r=i;
while(l>=1)
{
if(a[l-1]>a[i])l--;
else break;
}
while(r<=n)
{
if(a[r+1]>a[i])r++;
else break;
}
mx=max(mx,a[i]*(sum[r]-sum[l-1]));
}
printf("%lld\n",mx);
return 0;
}
然而，1e5的数据规模，要避免TLE，只能写O(n)或者O(nlogn)的算法。
推荐做数据不水的原题：POJ 2796 Feel Good
开l、r两个数组记录a[i]作为区间[ l [i] , r [i] ]内的最小值最远能扩展到的左端点l[i]和右端点r[i]，正逆遍历各一次，用两个双端队列分别求出 l [i] 和 r [i]，最后找最大值及其左右端点即可。
至于如何用单调队列的思想得到 l、r 数组，再详细说明一下。以找 r[i] 为例，遍历1~n，每次保证队尾是队列中的最小值，如果不是，则队尾出队，并记录以队尾为最小值时能扩展到的最远的右端点，遍历完之后剩下的队列中所有的位置对应的右端点都是n，比如说a[q.back()]是区间[q.back(),n]内的最小值，即r[q.back()]=n。
不知道为什么cin前面加了ios::sync_with_stdio(false)还是超时，改成scanf就好了，可能是POJ这题Special Judge的锅…
以下给出O(n)算法的单调队列优化代码：
#include <deque>
#include <cstdio>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll n,mx,ansl,ansr,a[N],l[N],r[N],sum[N];
deque<ll>q1,q2;
int main()
{
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
while(!q1.empty()&&a[q1.back()]>a[i])//每次保证队尾是队列中的最小值，如果不是，则队尾出队，并记录以队尾为最小值时所能扩展到的右端点
{
r[q1.back()]=i-1;
q1.pop_back();
}
q1.push_back(i);
}
while(!q1.empty())//剩下的队列中所有位置对应的右端点都是n
{
r[q1.back()]=n;
q1.pop_back();
}
for(int i=n;i>=1;i--)
{
while(!q2.empty()&&a[q2.back()]>a[i])
{
l[q2.back()]=i+1;
q2.pop_back();
}
q2.push_back(i);
}
while(!q2.empty())
{
l[q2.back()]=1;
q2.pop_back();
}
mx=0;
for(int i=1;i<=n;i++)
{
if(a[i]*(sum[r[i]]-sum[l[i]-1])>=mx)//注意有等于号，从而保证a[i]全部等于0的情况也会记录ansl和ansr
{
mx=a[i]*(sum[r[i]]-sum[l[i]-1]);
ansl=l[i];
ansr=r[i];
}
}
printf("%lld\n%lld %lld\n",mx,ansl,ansr);
return 0;
}
做完我们发现只对双端队列的尾部进行了操作，所以这题也可以用栈来解决，也就是所谓的“单调栈”。
投递中国南方电网等公司10个岗位 >