单调队列与优先队列

单调队列与优先队列的区别：单调队列的长度取决于输入数据的合法性，而优先队列的长度始终与输入数据的数量等同。而他们的单调性都是单调递减或单调递增。

单调队列 单调队列例题：https://www.luogu.org/problemnew/show/P1886

#include<cstdio> #include<iostream> #include<cmath> #include<deque> using namespace std; deque <int>win,num;//双端队列 win:单调队列 num:时间戳普通队列 int a[1000005],n,k; void maxx(){ win.clear();num.clear();//先清空两个队列 for(int i=1;i<=n;i++){//遍历所有数字 while(win.size()>0&&win.back()<a[i]){//如果窗口中有值(这个判断是为了防止窗口中一开始无值的情况)并且窗口的最后一个值比目前到达的真实数字小 win.pop_back();num.pop_back();//由于windows是单调队列 ,如果把a[i]直接放进去，会导致单调性错误 } //（我们要保证队列是单调递减队列，也就是说最后一个值是最小的，那么a[i必须比当前的值小，所以a[i必须不能大于队列的最后一个值 win.push_back(a[i]);num.push_back(i);//上面已经保证了队列的单调性，所以可以直接添加值 if(num.front()==i-k){win.pop_front();num.pop_front();}//如果时间戳刚好到了i-k，也就是到了窗户的前面（窗户本身是没有厚度的，因此不需要考虑窗户边的情况 if(i>=k)cout<<win.front()<<" ";//这里的判断是为了防止窗户还没造完就开始输出的情况 } cout<<endl; } void minn(){//同理。 win.clear();num.clear(); for(int i=1;i<=n;++i){ while(win.size()>0&&win.back()>a[i]){win.pop_back();num.pop_back();} win.push_back(a[i]);num.push_back(i); if(num.front()==i-k){win.pop_front();num.pop_front();} if(i>=k)cout<<win.front()<<" "; } cout<<endl; } int main(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; minn(); maxx(); return 0; }

优先队列