安徽建筑大学城市建设学院网站,我国网站建设现状,四川住房建设厅网站增项查询,公众号入口官网单调队列模板题#xff1a;
所需知识#xff1a;单调队列
利用双端队列来实现单调队列#xff1b;
双端队列与普通队列的不同处#xff1a;双端队列删除元素时既可以删除队头又可以删掉队尾#xff0c;其可以较好的维护单调队列的单调性#xff1b;
双端队列的定义及…
单调队列模板题
所需知识单调队列
利用双端队列来实现单调队列
双端队列与普通队列的不同处双端队列删除元素时既可以删除队头又可以删掉队尾其可以较好的维护单调队列的单调性
双端队列的定义及主要函数
dequeintq;
q.push_front();//队头插入一个元素
q.push_back();//队尾插入一个元素
q.pop_front();//删除队头元素
q.pop_back();//删除队尾元素
q.front();//返回队头元素
q.back();//返回队尾元素
q.size();//返回队列大小
q.empty();//判断队列是否为空若为空则返回true反之返回false
q.clear();//清空队列
q[i];//返回下标为i的元素
思路构建一个单调队列并维护其单调性即使队列里面的元素严格单调若为单调递增且a[i]a[q.back()]则将队尾元素删除反之若为单调递减则当a[i]a[q.back()]时删除依次将每个元素下标入队当队首元素已离开区间时删除队头最后在区间长度达到k之后输出每个区间对应的最小值与最大值。
#include iostream
#include cstring
#include algorithm
#includequeue
const int N1e610;
typedef long long ll;
using namespace std;int n,k;
int a[N];
dequeintq;
int main()
{cinnk;for(int i1;in;i)cina[i];for(int i1;in;i){//i为区间尾的下标//维护队列单调性while(!q.empty()a[q.back()]a[i]) q.pop_back();//若队头不在区间内则删除if(!q.empty()q.front()ki) q.pop_front();q.push_back(i);//当区间长度大于k时才输出if(ik) couta[q.front()] ;} coutendl;//清空队列q.clear();for(int i1;in;i){//维护队列单调性while(!q.empty()a[q.back()]a[i]) q.pop_back();//若队头不在区间内则删除if(!q.empty()q.front()ki) q.pop_front();q.push_back(i);//当区间长度大于k时才输出if(ik) couta[q.front()] ;}return 0;
}
