单调队列(利用C++容器deque实现)原理解析
程序员文章站
2022-07-07 15:46:27
...
1:关于deque
*deque是C++中的一个容器,其底层原理是双端队列(学过数据结构的应该知道,就是对比于普通的队列而言,可以在双端队列的两端进行插入和删除操作,所以用它来操作数据比较方便,但是注意:其底层存储结构并不是连续的存储单元,所以不能用指针加偏移地址去操作)。
* 其头文件为#include< queue >
2:关于单调队列
单调队列其实是一种思想,也就是维护一个单调递增或者单调递减的队列,如果新插入的值比队尾大,就可以直接插入队列,如果比队尾小,就将队尾弹出,知道队尾元素小于这个插入值。所以即可维护一个单调队列。单调队列可以用来计算某个区间内部的最大值或者最小值。
3:利用deque实现单调队列
根据deque的特点,我们可以很清楚的模拟出实现单调队列的过程。
4:例题
//@author:hairu,wu
//@from:ahut
#include<iostream>
#include<queue>
using namespace std;
int n,m;
struct E{
int num;
int id;
};
deque<E> q;
int main(){
cin >> n>> m;
E e;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
e.num=x;e.id=i;
if(i==1){//第一个特别输出
q.push_back(e);
printf("0\n");
continue;
}
//对于本题,需要弹出队头在前m个数字之外的数弹出
while(!q.empty()&&q.front().id<=i-m-1){
q.pop_front();
}
//输出在前m个中最小的数字
printf("%d\n",q.front().num);
//维护单调队列,如果x大于等于队尾元素,直接插入,如果小于队尾元素,则需要弹出对微元素
while(!q.empty()&&q.back().num>=x){
q.pop_back();
}
q.push_back(e);
}
return 0;
}
上一篇: 2345看图王怎么批量添加水印?
下一篇: 美图秀秀制作流光字(闪闪发亮)全程图解