建盏/夫唯seo视频教程

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;
}