文章目录

• 单调队列
• 单调队列适用的范围
• 例题

单调队列

我们都已经知道了队列是一种先进先出的结构，单调队列顾名思义就是一种递增或递减的队列。由于所用的元素各入队出队一次，所以它的时间复杂度是O(n)。

单调队列适用的范围

那么我们通常在什么情况下才会使用单调队列呢？
一般会在求一定范围内的最大值或最小值考虑单调队列，（当然线段树也可以在nlog(n)的时间内做到)

例题

下面我们以一个例题来讲解如何使用单调队列 洛谷P1886 滑动窗口 (点击可进入洛谷官网提交)。
题目大意：
有一个长为 n 的序列 a，以及一个大小为 k 的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。
输入n,k,和序列a,其中n为序列a的大小，k为窗口大小。（1<=k<=n<=10⁶）
输出每次窗口滑动的最大值和最小值。

读懂题目意思我们很快就能想出一个暴力破解的思路，每次都枚举一个大小为k的区间，然后比出最大值，但是这样时间复杂度会高达O(nm)，妥妥的超时。

思路：
到了这里我们想是不是可以维护一个队列que（因为我们从前往后遍历a，满足先进先出的条件，考虑使用队列），que维护的内容为结构体，结构体的内容为元素的大小和下标，que.front()是对应窗口的最大值，我们遍历这个序列a，如果当前que的头部元素不在这个窗口所对应的范围内（即下标超界），那么就可以从que头部弹出该元素了(que.pop_front())，假设当前遍历到的元素a[i]，如果a[i]>=que.back(),那么说明a[i]比que.back()更有资格成为当前窗口的最大值，所以可以抛弃尾部元素了（que.pop_back()）,直到a[i]<que.back()，则将该元素加入que的尾部（que.push_back(a[i])），用while循环可以轻易实现这一步骤。到了这里我们就O(n)的时间内求出了所有的窗口最大值， 最小值也可以用同样的思路求出来，仔细观察一下que内部维护的值，我们发现它的元素的值满足单调递减的规律，所以它是一个单调队列。.

不多说了，直接上AC代码。

#include <iostream>#include <queue>#include <cstdio>using namespace std;const int maxn=2e6+286;int st[2][2002000]; //用于存储答案typedef struct node   //定义结构体用于存储元素的下标和大小{  int id,val;  //下标、大小};  node a[maxn]; //用于储存序列adeque<node> que1,que2;  //que1维护最大值，即单调递减的队列（头部元素是最大值）   //que2维护最小值，即单调递增的队列（头部元素是最小值）int main(){int n,k;    int cnt=0;    scanf("%d%d",&n,&k);    for(int i=1;i<=n;i++)     //读入序列a    { scanf("%d",&a[i].val); a[i].id=i;    }    for(int i=1;i<=n;i++)     //遍历序列a    { /* 如果a[i]>=que.back(),那么说明a[i]比que.back()更有资格成为当前窗口的最大值， 所以可以抛弃尾部元素了（que.pop_back()） */  while(!que1.empty()&&a[i].val>=que1.back().val)  que1.pop_back(); /* 如果a[i]<=que.back(),那么说明a[i]比que.back()更有资格成为当前窗口的最小值， 所以可以抛弃尾部元素了（que.pop_back()） */  while(!que2.empty()&&a[i].val<=que2.back().val)que2.pop_back();   que1.push_back(a[i]);  //将当前元素加入que  que2.push_back(a[i]);   while(i-k>=que1.front().id)que1.pop_front();    //当前维护的头部元素不在窗口的范围内，即下标越界了，删除头部元素  while(i-k>=que2.front().id)que2.pop_front(); if(i>=k)   //存储答案 {     st[1][++cnt]=que1.front().val;     st[0][cnt]=que2.front().val; }    }    //输出答案    for(int i=1;i<=cnt;i++) printf("%d ",st[0][i]);    printf("\n");    for(int i=1;i<=cnt;i++) printf("%d ",st[1][i]);    return 0;}

希望在这里你能对单调队列有了进一步的了解，有所收获。
祝学习顺利！！！