其实单调队列就是一种队列内的元素有单调性的队列,因为其单调性所以经常会被用来维护区间最值或者降低dp的维数已达到降维来减少空间及时间的目的。
每一个答案只与当前下标的前m个有关,所以可以用单调队列维护前m的个最小值,
考虑如何实现该维护的过程??
显然当前下标(x)的(m)个以前的元素(即下标小于(x-m+1)的元素)在范围外,和答案没什么太大联系,所以可以将其从队列中删除。
对于两个元素(a),(b),下标分别为(a),(b),如果有(a>=b)&&(a<b)那么b留在队列里肯定优于(a),因此可以将(a)删除。
维护队首:如果队首已经是当前元素的(m)个之前,将(head)++,弹出队首元素
维护队尾:比较(q[tail])与当前元素的大小,若当前元素更优(tail)++,弹出队尾元素,直到可以满足队列单调性后加入当前元素。
考虑单调队列的时间复杂度:由于每一个元素只会进队和出队一次,所以为(o(n))。
p1440 求m区间内的最小值
p1886 滑动窗口 /【模板】单调队列
p3088[usaco13nov]crowded cows s
#include <bits/stdc++.h> using namespace std; int a[2000100]; bool b[2000100]; int q[2000100];//数组模拟队列,更好调试 int head=1,tail=0; int n,m; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); } for(int i=1;i<=n;i++) { while(i-q[head]+1>m&&head<=tail)//若头结点在范围外 { head++;//弹出头结点 } while(a[i]<a[q[tail]]&&head<=tail)//若当前节点优于尾节点 { tail--;//弹出尾结点 } q[++tail]=i;//当前节点入队 } return 0; }
利用单调队列,可以优化涉及定长连续子区间求最值的线性dp问题
例题
p1725 琪露诺 琪露诺是最强的!!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/599616.html