静坐观心,真妄毕现
单调队列就是,有单调性的队列。分为两种,一种是单调递增,另一种是单调递减。一般来说,队列的队首是整个队列的最大值或者最小值(废话)。
百度的解释:不断地向缓存数组里读入元素,也不时地去掉最老的元素,不定期的询问当前缓存数组里的最小的元素。
用单调队列来解决问题,一般都是需要得到当前的某个范围内的最小值或最大值.
手动推导
7 6 8 12 9 10 3
求最大值
i=0*i*=0,队列初始化0,队列为{0}
i=1*i*=1,因为7>07>0,所以7入队,0出队(要维护这个队列单调递减),队列为{7}
i=2*i*=2,因为6<76<7,所以6入队,队列为{7,6}
i=3*i*=3,因为8>68>6,所以6出队,8>78>7,所以7出队,8入队,队列为{8}
i=4*i*=4,因为12>812>8,所以8出队,12入队,队列为{12}
i=5*i*=5,因为9<129<12,所以9入队,队列为{12,9}
i=6*i*=6,因为10>910>9,所以9出队,10<1210<12,所以10入队,队列为{12,10}
i=7*i*=7,因为3<103<10,所以3入队,队列为{12,10,3},但是,因为12的位置为4,不在(i-3,i](*i*−3,*i*],这个范围内,所以出队,队列为{10,3}
这时就有人奇怪了,队列里剩下的不是最大值呀
其实不难发现,每个队列的队头就是当前的最大值,所以只要每次更新完队列后让更新前的最大值与更新后的最大值比较就行
最小值同理
板子
#include<bits/stdc++.h>
const int N=200010;
using namespace std;
int n,m,l,r;
int a[N],q[N];
int main()
{
scanf("%d",&n);
scanf("%d",&m);
for(int i =1;i<=n;++i)
a[i] = in();
cout<<'0'<<endl;
l=1,r=1;//初始化
q[1] =1;
for(int i=2;i<=n;++i)
{
while(l<=r && q[l]+m<i) ++l;
printf("%d\n",a[q[l]]);
while(l<=r && a[i]<a[q[r]]) --r;
q[++r]=i;//储存位置
}
system("pause");
return 0;
}
STL版
deque<int> q;
q.push_back(0),b[0] = 0;;
for(int i =1;i<=n;++i)
{
//前缀和
b[i] = b[i-1] + a[i];
//while(!q.empty()&&q.front()+m<i) m = n
// q.pop_front();
//求区间[q.front,i]连续和,并更新最大值。
ans = max(ans,b[i]-b[q.front()]);
//维护队列单调性
while(!q.empty()&&b[i]<=b[q.back()])
q.pop_back();
//当前元素入队
q.push_back(i);
}