大家好，欢迎来到IT知识分享网。
我们去食堂排队打饭的时候，很想去看看今天有什么菜，但是，能不能看到菜和身高有关。如果前面的人比你高，你就看不到菜了。
这时候，你突然发动“超能力”，从后往前依次把队列中身高比你高的人全赶跑了，最终当你把队列处理完毕时你再入队，你就是队列中“最高”的人了。
假设队伍中的每个人都拥有这个“超能力”，那么每个人进入队伍时，都会将身高比他高的人赶走，最终队伍会满足单调性：
从队头到队尾，依次从矮到高。
上述描述的过程就是单调队列的产生过程。
单调队列介绍
单调队列中的元素是单调有序的，这一点在上文的描述中已经体现。因此，单调队列的特点之一就是维护区间极值。
以单调递增的队列为例，队首一直是极小值，因此在区间内查找极值的时间复杂度为O(1)。
我们发现，在创建单调队列时，队尾元素需要能入队出队，队头元素也需要出队（打饭完成出队），因此单调队列一般用双端队列deque来实现。
由于数据的不断入队出队，单调队列可以用来维护一段区间内的最值。如果区间长度固定，那就能够维护滑动窗口中的最值，这也是单调队列的经典应用。
在维护单调队列的过程中，每个元素只会入队和出队一次，因此维护单调队列的时间复杂度为O(n)。
单调队列的维护过程演示
以队列{12,34,23,78,89,-8,19,55}为例，开始维护单调递增的对应单调队列：
（1）首先12入队，队列中有{12}；
（2）34比12大，34入队，更新队列为{12,34}；
（3）23比34小，34出队，23再入队，更新队列为{12,23}；
（4）78比23大，78入队，更新队列为{12,23,78}；
（5）89比78大，89入队，更新队列为{12,23,78,89}；
（6）-8比队列中任何元素都小，因此循环将所有元素从队尾出队后，-8入队，更新队列为{-8}；
（7）19比-8大，19入队，更新队列为{-8,19}；
（8）55比-8大，55入队，更新队列为{-8,19,55}；
在维护过程中，始终保持队首元素为当前已出现的所有元素的最小值。
但如果只是为了找一个数列中的最小值，没必要动用单调队列，因此单调队列一般用于在滑动窗口中寻找最值，接下来结合例题1介绍维护单调队列的过程与代码模版。
例题：
滑动窗口 /【模板】单调队列
算法解析
1、先不考虑单调队列，使用普通的算法来试试看。从头到尾扫描，每次检查k个数里的最小值和最大值，时间复杂度为O(nk)。
【参考代码】
#include
#include
using namespace std; long long a[]; long long maxx[],minn[]; int n,k; int main(){ cin>>n>>k; for(int i=0;i
>a[i]; } for(int i=0;i+k<=n;i++){ //是从a[0]开始存储数组的，因此最后一个窗口的起点下标是n-k //如果是从a[1]开始存储的话，最后一个窗口的起点下标是n-k+1 maxx[i]=-1<<31,minn[i]=1<<31-1; for(int j=i;j<i+k;j++){ maxx[i]=max(maxx[i],a[j]); minn[i]=min(minn[i],a[j]); } } for(int i=0;i<n-k+1;i++){ cout<<minn[i]<<" "; } cout<<endl; for(int i=0;i<n-k+1;i++){ cout<<maxx[i]<<" "; } return 0; }
（左右滑动查看完整代码）
评测结果如下：
由于数据较水，大部分测试点也能通过。想要AC的话，还得使用单调队列。
2、以样例数据为例，先展示单调队列求窗口最小值的算法流程：
（1）初始队列为{1,3,-1,-3,5,3,6,7}，先将1入队，初始队列为{1}；
（2）3>1，3入队，更新队列为{1,3}；
（3）-1<3同时-1<1，因此3和1依次从队尾出队，-1入队，同时这是第1个窗口，输出队首-1，队列为{-1}；
（4）-3<-1，因此-1从队尾出队，-3入队，输出队首-3，并更新队列为{-3}；
（5）5>-3，入队，输出队首-3，并更新队列为{-3,5}；
（6）3<5，5从队尾出队，3入队，输出队首-3，并更新队列为{-3,3}；
（7）6>3，入队，更新队列为{-3,3,6}，这里就出现问题了。
由于-3不在当前窗口中，因此需要-3从队首出队。但是，如何判断-3在不在窗口中呢？
在上面的流程中，都是直接将值作为队列元素入队，但是没有很好的办法来查找这个元素对应的数组下标。
因此，需要入队的不是元素的值，而是元素的下标，这样就方便判断元素是否在窗口中了。
结合上述的改进，再用一张表格展示完整的单调队列维护过程：
在本例题中还需注意，等第一个窗口的元素完全入队后，才能进行第一次输出。因此在判断队首是否在窗口内和输出前都要加上判断i>=m。
【参考代码】
#include
#include
using namespace std; int a[]; deque
q; int main(){ ios::sync_with_stdio(0); //加快cin、cout速度 int n,k; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ whileq.empty aq.back>=a[i]){ //这里注意细节，如果队尾的值与当前值相等，也要让后来的入队 q.pop_back(); } q.push_back(i); //注意入队的是数组下标 if(i>=k){ //第一个窗口完全入队后再输出 while(q.front()<=i-k){ //为保险这里也可以加上判断：队列不为空 q.pop_front(); //如果队头不在窗口，队头出队 } cout<<a[q.front()]<<" "; } } cout<<'\n'; while(!q.empty()){ //清空deque，为求最大值做准备 q.pop_front(); } for(int i=1;i<=n;i++){ //滑动窗口找最大值，代码与上面镜像 while(!q.empty() && a[q.back()]<=a[i]){ q.pop_back q.push_backi ifi>=k){ while(q.front()<=i-k){ q.pop_front(); } cout<<a[q.front()]<<" "; } } cout<<'\n'; return 0; }
（左右滑动查看完整代码）
评测结果如下：
与普通的算法相比，在时间复杂度和空间复杂度上都有显著的提升。
本题使用单调队列算法的时间复杂度为O(n)，空间复杂度为O(n+k)。
例题2：
扫描
算法解析
根据题目的描述，很容易发现其为滑动窗口问题，并且是求滑动窗口最大值，可以使用单调队列求解。具体算法实现和例题1一致，因此不再赘述。
例题1中展示的代码是从a[1]开始赋值的数组，这里将展示从a[0]开始赋值数组的单调队列代码。读者们可以根据自己的编程习惯选择性掌握内容。
【参考代码】
#include
#include
using namespace std; int a[]; deque
q; int main(){ ios::sync_with_stdio(0); //加快cin、cout速度 int n,k; cin>>n>>k; for(int i=0;i
>a[i]; } for(int i=0;i<n;i++){ while(!q.empty() && a[q.back()]<=a[i]){ q.pop_back q.push_backi ifi>=k-1){ //这里是核心代码唯一的不同点 while(q.front()<=i-k){ //同样这里可以加上!q.empty() q.pop_front(); } cout<<a[q.front()]<<endl; } } return 0; }
单调栈是始终保持栈内元素是单调递增或单调递减的栈，主要用于寻找左侧（或右侧）第一个比当前元素大（或小）的元素问题。
单调栈相较于单调队列要更为简单，因此读者们对本期的单调队列理解透彻的话，下期内容的掌握会更加简单。
如果对单调队列应用还不熟练的读者，可以在洛谷上尝试P1440、P2629、P2422、P2251等单调队列的经典题，巩固算法。
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/175929.html
