单调队列，即单调递减或单调递增的队列。
1. 队列中的元素在原来的列表中的位置是由前往后的(随着循环顺序入队)。
2. 队列中元素的大小是单调递增或递减的。
从队尾入列，队首或队尾出列。
那么单调队列用什么用呢？单调队列一般用于求区间内的最值问题。看几道题，理解上述内容：
1. 洛谷P1886 滑动窗口：https://www.luogu.org/problemnew/show/P1886
看上去不是很难，两个for循环就搞定了，但要知道这样的算法时间复杂度为o(n^2)，按题目所给的数据肯定会超时。我们要的是时间复杂度为o(n)的算法，看代码：
#include <bits/stdc++.h> using namespace std; const int N=1e6+5; int m[N]; //用于储存最大值序列 struct node{ //队列的节点，包含元素在列表中原来的位置和值 int order; int value; }tmp; deque<node>maxn,minn; //定义节点类型单调队列，分别记录区域内最大值和最小值 int main() { int n,k,t; //n,k如题目中含义，t用于暂时储存输入 int m_lo=0; //最大值序列下标 scanf("%d%d",&n,&k); for(int i=0;i<n;i++) { scanf("%d",&t); if(!maxn.empty() && i-maxn.front().order>=k) maxn.pop_front(); //单调队列的原理部分 if(!minn.empty() && i-minn.front().order>=k) minn.pop_front(); //具体看下方说明 while(!maxn.empty() && maxn.back().value<t) maxn.pop_back(); while(!minn.empty() && minn.back().value>t) minn.pop_back(); tmp.value=t; //节点入列 tmp.order=i; maxn.push_back(tmp); minn.push_back(tmp); if(i>=k-1) //当达到题目要求区间长度时就开始输出最小值序列，并储存最大值序列 { if(i==n-1) printf("%d\n",minn.front().value); else printf("%d ",minn.front().value); m[m_lo++]=maxn.front().value; } } for(int i=0;i<m_lo;i++) //输出最大值序列 { if(i==m_lo-1) printf("%d\n",m[i]); else printf("%d ",m[i]); } }说明：这道题，求的是一个区间内的最大值和最小值。对于数组中的某一个元素，我们只要关心它自己和它前k-1个数即可。
那么如何用队列处理呢？先简单说一下解题思路，以求最小值为例：一开始数组下标i为0，我们向队列里不停的放元素，并且一直保持队首位元素为最小值，直到第k个数，此时队首元素即为前k个数的最小值。然后我们把队首输出。继续往下走，走的过程中把队列中下标超出(i-k+1)~i区间范围的数踢掉，继续保持队首元素为区间内最小值，然后输出队首元素。
简单归纳一下，对于每一次循环，我们要做的就是：先踢掉超出区间范围的元素，放入元素并保证队首为数组中当前区间的最小值，输出队首，往复。队列内储存的就是放入元素之前区间内单调递增的最小值序列。
那么我们要解决的问题有两个：
1. 如何去除超出区间范围的元素：这就是代码中node节点的作用了，node节点中储存了原数组的下标，对于每一次新输入的第i个数，因为单调队列内元素位置是从前到后的，我们只要将队首元素的node.order和i进行判断，看此时是否i-node.order>=k即可，是就让队首元素出列。
2. 如何保证队首元素为区间内最小值：对于某一区间，我们每输入一个数，就看看队尾元素的值是否比它大，是就让这个元素出列，直到队列为空或者队尾元素值比这个数小，然后我们把这个数放进去，这个时候队首元素即为区间最小值，输出即可。
合理性分析：从队列为空开始，我们放入第0个数，一直到k-1，每一次输入的时候都让队尾值比当前输入值小的出列，很容易知道此时队首就是[0,k-1]的最小值。那么接下来输入第k个数，可以肯定的是区间[1,k]的最小值与[0,k-1]的最小值有关。有两种情况，一是[1,k]的最小值来自k前面的数，这种情况下，我们看[0,k-1]的情况，若[0,k-1]的最小值来自第0位，就说明队列里肯定有除第0个元素外的元素，即队列里肯定有[1,k-1]的最小值序列，且它们是单调递增的。此时由于第0位超出区间范围，出列，不影响区间[1,k]最小值的查找。若[0,k-1]的最小值来自[1,k-1]，自然不影响[1,k]最小值的查找。二是最小值就是k，那么进行操作即可把队列清空，再把它放进即可，此时队首就是k，即最小值。对于一般性的情况，同样有上述关系。
要注意的点：
1. 写if和while的时候一定要先写判断队列是否为空，否则if和while中会进行溢出操作。
2. 判断队首是否出队和队列长度没有确定关系，因为队列不一定都包含了整个区间的元素。
3. 对于重复元素去不去除都可以，去除可以保证队列中至少有一个，不去除不影响队首，且在遇到更小的值时都会出队。
4. 这个算法只有一个for循环，且每个元素都只出入一次，所以时间复杂度为o(n)。
2. P1440 求m区间内的最小值：https://www.luogu.org/problemnew/show/P1440
这道题题目可能说的不是很清楚，看样例：4的前两个数中最小值是1，3的前两个数中最小值也是1。
这题和上一题基本一样，不同的是这回窗口不包括当前元素，即当前元素不参与比较，每一次循环输出上一次的结果即可。
#include <bits/stdc++.h> using namespace std; const int N=2e6+5; int a[N]; struct node{ int order; int value; }tmp; deque<node>vis; int main() { int n,m; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&a[i]); tmp.order=i; tmp.value=a[i]; if(i==0) printf("%d\n",0); else printf("%d\n",vis.front().value); if(i-vis.front().order>=m) vis.pop_front(); while(!vis.empty() && vis.back().value>a[i]) vis.pop_back(); vis.push_back(tmp); } }3. P2032 扫描：https://www.luogu.org/problemnew/show/P2032
模板题，直接写：
#include <bits/stdc++.h> using namespace std; struct node{ int order; int value; }tmp; deque<node>vis; int main() { int n,k,t; scanf("%d%d",&n,&k); for(int i=0;i<n;i++) { scanf("%d",&t); if(!vis.empty() && i-vis.front().order>=k) vis.pop_front(); while(!vis.empty() && vis.back().value<t) vis.pop_back(); tmp.order=i; tmp.value=t; vis.push_back(tmp); if(i>=k-1) { printf("%d\n",vis.front().value); } } }4. P1714 切蛋糕：https://www.luogu.org/problemnew/show/P1714
这题乍一看好像可以用尺取做，但其实不行，因为左右指针移动后是没有办法回退的。
那么这题怎么用单调队列呢？首先要将问题转化成当前位置所有元素和减去前x个元素和最大值的问题。要得到最大值，只需要前x个元素和最小。那么我们把数组每一位都换成从0~当前位置的和，利用单调队列求当前元素前的元素的最小值，然后用当前元素值减去最小值，每次进行比较即可。
#include <bits/stdc++.h> using namespace std; const int N=1e6+5; int a[N],sum[N]; struct node{ int order; int value; }tmp; deque<node>vis; int main() { int n,m; int ans; scanf("%d%d",&n,&m); for(int i=0;i<n;i++) { scanf("%d",&a[i]); if(i==0) sum[0]=a[i]; else sum[i]=sum[i-1]+a[i]; if(!vis.empty() && i-vis.front().order>m) vis.pop_front(); //注意为 > ，自行理解 while(!vis.empty() && vis.back().value>sum[i]) vis.pop_back(); tmp.value=sum[i]; tmp.order=i; vis.push_back(tmp); if(i==0) ans=sum[i]-vis.front().value; else if(i<m) ans=max(ans,sum[i]); else ans=max(ans,sum[i]-vis.front().value); } printf("%d\n",ans); }5. P1725 琪露诺：https://www.luogu.org/problemnew/show/P1725
这题估计在出题的时候就有bug，不过不用管，因为数据就是按有bug的方法给的。
首先这是一道dp题，状态转移方程为dp[i]=max(dp[x])+a[i]; 其中(i-r)<=x<=(i-l);
由于要求区间dp[i-r]~dp[i-l]内的最大值，所以用到单调队列。
循环直接从l开始，因为l之前的位置走不到，dp值都为0。
单调队列要维护的是dp的最大值(注意不是a的)，且要维护区间的下限与i相差l(这就是定义j的原因)，区间固定长度为r-l+1。
#include <bits/stdc++.h> using namespace std; const int N=1e6+5; int a[N],dp[N]; struct node{ int order; int value; }tmp; deque<node>vis; int main() { int n,l,r; scanf("%d%d%d",&n,&l,&r); for(int i=0;i<=n;i++) scanf("%d",&a[i]); for(int i=0;i<l;i++) a[i]=0; //从0到l-1是走不到的，所以把值改为0 for(int i=n+1;i<=n+r;i++) a[i]=0; int j=0; //j是要维护的元素下标 for(int i=l;i<=n+r;i++) { if(!vis.empty() && j-vis.front().order>=r-l+1) vis.pop_front(); while(!vis.empty() && vis.back().value<dp[j]) vis.pop_back(); tmp.order=j; tmp.value=dp[j]; vis.push_back(tmp); dp[i]=vis.front().value+a[i]; j++; } int ans=-9999999; for(int i=n+1;i<=n+r;i++) { ans=max(ans,dp[i]); } cout<<ans<<endl; }6. P2629 好消息，坏消息：https://www.luogu.org/problemnew/show/P2629
这题同样要用到元素和，思路是将a复制一遍放到数组末尾，然后再滑动大小为n的窗口，找窗口内的最小值，减去窗口前方值的和，看是否大等于0。
#include <bits/stdc++.h> using namespace std; const int N=2e6+5; int a[N],sum[N]; struct node{ int order; int value; }tmp; deque<node>vis; int main() { int n,k,ans; cin>>n; for(int i=0;i<n;i++) { scanf("%d",&a[i]); a[i+n]=a[i]; if(i==0) sum[i]=a[i]; else sum[i]=sum[i-1]+a[i]; } for(int i=n;i<2*n;i++) sum[i]=sum[i-1]+a[i]; k=0; //k用于记录窗口前的位置下标 ans=0; for(int i=0;i<2*n-1;i++) { if(!vis.empty() && i-vis.front().order>=n) vis.pop_front(); while(!vis.empty() && vis.back().value>sum[i]) vis.pop_back(); tmp.order=i; tmp.value=sum[i]; vis.push_back(tmp); if(i==n-1 && vis.front().value>=0) ans++; else if(i>n-1 && vis.front().value-sum[k]>=0) ans++; if(i>n-1) k++; } cout<<ans<<endl; }7. P2422 良好的感觉：https://www.luogu.org/problemnew/show/P2422
这道题的思路是找到数组a中在以每一个a[i]为最小值的情况下最多能包含多大的区间(因为所有值都大于0，所以在最小值为a[i]的情况下，要尽可能让区间[i,j]范围最大，这样a[i]乘以区间内元素的和就最大)，然后比较每一个a[i]与对应区间内元素和的乘积即可，难点在于区间范围的求取。
在这道题中，单调队列的作用是构造一个a的单调递增的序列。对于入队的每一个元素，如果它小于队列的尾元素，说明尾元素的区间下限已经确定，即尾元素本身，而尾元素的区间上限就是队列中尾元素的前一个数，下限的sum值和上限的sum值相减，就得到在以a[i]为最小值的情况下能包含的最大区间的元素和。其它特殊情况参照代码。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N=3e6+5; LL a[N],sum[N],multi[N]; struct node{ LL order; LL value; }tmp; deque<node>vis; int main() { LL n,lo,bef,aft,ans; cin>>n; for(int i=0;i<n;i++) { scanf("%lld",&a[i]); if(i==0) sum[i]=a[i]; else sum[i]=sum[i-1]+a[i]; } a[n]=0; //这个很重要，否则到最后一个数的时候队列没办法清空 for(int i=0;i<=n;i++) //注意是<=，原因和上面一样 { while(!vis.empty() && vis.back().value>a[i]) { lo=vis.back().order; aft=i-1; vis.pop_back(); if(!vis.empty()) bef=vis.back().order; else bef=-1; if(bef==-1) multi[lo]=sum[aft]; else multi[lo]=sum[aft]-sum[bef]; } tmp.order=i; tmp.value=a[i]; vis.push_back(tmp); } ans=-1; for(int i=0;i<n;i++) { ans=max(ans,multi[i]*a[i]); } cout<<ans<<endl; }
