单调队列这一字眼进一步理解
明显的单调性
基于近期复刷的单调队列题目，形如经典的模版题目P1886 【模板】单调队列 / 滑动窗口 ，以及对此进行的变式
P1714 切蛋糕 ,P1638 逛画展
P1886的模版题让我重新回顾了一下如何维护一个单调区间，在这道题中维护单调区间的意义是为了保持其当前窗口的最大值为队首，队首则是依次为更小的值，这样的区间有一个特点，如果当我们队首因为离开了窗口内范围而跳脱，此时新队首会成为新的最大，而当我们窗口进行移动时，如果新来的值的大小有点大，我们就依次对队尾元素进行比较后让他们pop()，毕竟他们这么小已经没有可能作为当前窗口的最大值了。我们找每个时期的最小值也是同样的道理。
这样的题目常用双端队列
deque进行解答，对于我这种初学者来说单调队列的队列一词感觉有所误导因为初学者对队列的印象大都停留在先进先出的效果，单调区间更感觉符合我们想要的效果，感觉有点抽象。单调队列=单调栈+滑动窗口
int n,k; cin >> n >> k; vector<int>a(n+1); vector<int>ans_mx; vector<int>ans_mi; deque<int>mx; deque<int>mi; for(int i=1;i<=n;i++) { cin >> a[i]; } for(int i=1;i<=n;i++) { while(!mx.empty()&&i-k>=mx.front()) { mx.pop_front(); } while(!mx.empty()&&a[mx.back()]<=a[i]) { mx.pop_back(); } while(!mi.empty()&&i-k>=mi.front()) { mi.pop_front(); } while(!mi.empty()&&a[mi.back()]>=a[i]) { mi.pop_back(); } mx.push_back(i); mi.push_back(i); if(i>=k) { ans_mx.push_back(a[mx.front()]); ans_mi.push_back(a[mi.front()]); } }核心代码其实就几行，但在干一件有点难说清楚的事，我捋捋：
首先这题让我们判断窗口大小固定为k，自发地向右移动的过程这个窗口内的最大或最小值，我去那我直接每次移动都直接暴力检索最值，不行不行，这样直接TLE。从正解来理解，我们在做一个这样的事情假如当前的窗口是一个从大到小的区间（从左往右）我们可以发现这样单调的区间每次最大的（最左的）那个数因为离开了窗口的大小范围
pop紧接着因为区间是单调的所以下一个数就是最大的值，但是如果此时下一个进入窗口的数明显的打乱了单调性，来了个相当大的值怎么办？这个值会影响其他满足前一时刻单调性的值成为最大值的可能性，所以我们需要把这一时刻区间内不再可能成为最大值的数据删除，重新让这个区间的单调性保持从大到小。
隐藏的单调性
接下来我们看P1714切蛋糕一题，这一题的解法还是核心单调队列，但这不一样的是单调性表现需要用前缀和看出来
简单说下题目意思，意思就是类比上题这题我们也当做一个滑动窗口，然后我们需要在窗口里找到和最大的区间注意区间是连续的（固定区间的最大连续子段和），当然暴力依然TLE，我们需要用单调队列的方法降低到O(n)
int n,m; cin >> n >> m; vector<int>a(n+1); vector<int>sum(n+1,0); deque<int>q; for(int i=1;i<=n;i++) { cin >> a[i]; sum[i]=sum[i-1]+a[i]; } q.push_back(0); int ans=-LLONG_MAX; for(int i=1;i<=n;i++) { while(!q.empty()&&i-m>q.front()) { q.pop_front(); } ans=max(ans,sum[i]-sum[q.front()]); while(!q.empty()&&sum[q.back()]>=sum[i]) { q.pop_back(); } q.push_back(i); } cout << ans << endl;我们依旧从代码入手，很明显我们可以发现核心代码与模版题目的及其相似都是在对头与尾进行操作，==
sum[q.back()]>=sum[i]==这一步是整个单调性维护的核心。其实这道题的核心跟上一题是一样的，我们都要保持队首的一个最值状态，因为我们要最大话sum[i]-sum[q.front()]，所以我们需要让sum[q.front()]的值最小化，那我们有更小的sum选手不就应该淘汰前边没用的家伙吗。
难发现的单调性队列
再看P1638逛画展这一道并没有单调性但跟单调队列的思想相似的一道题，我看了题解做法多是双指针，学完单调队列后发现可行便写了下来。
题目意思让你在n大小的数组里用最小的区间包含1-m的数的左端点跟右端点。
int n,m; cin >> n>> m; vector<int>a(n+1); vector<int>num(m+1,0); deque<int>q; for(int i=1;i<=n;i++) { cin >> a[i]; } int k=0; int ans=LLONG_MAX; int l=1,r=n; for(int i=1;i<=n;i++) { q.push_back(i); num[a[i]]++; if(num[a[i]]==1)k++; while(!q.empty()&&k==m) { if(ans>q.size()) { l=q.front(); r=q.back(); ans=q.size(); } num[a[q.front()]]--; if(num[a[q.front()]]==0)k--; q.pop_front(); } } cout << l << " " << r;这里不一样的是对队列操作并没有对队尾进行pop而是与循环次数同时进行push所以直接用queue就行
思路就是我们从最左段开始扩展我们的区间大小等到区间内包含所有数时（用桶数组进行计数），让队首进行
pop直到区间内不包含所有数时继续让数据进行入队，这个核心思想其实跟双指针是一样的。
更正：
我发现这一题我的代码其实就是普通队列加上双指针的思想，双端队列的写法应该是在队首跟队尾相同时将队头排出使得整个队伍的长度尽可能的小。单调队列的写法所维护的是队首在队内出现的次数为1。
总结
单调队列的题目能从题目大致看出，滑动窗口+最值这样的搭配一般优先考虑优先队列，我们来回顾一下第一道明显单调性的单调队列，很明显我们是通过维护一个单调的队列让队首保持一个最值的状态从而显现出我们的每个时期的答案。再看下一道隐藏单调性的题目，我们用的是一个前缀和的作差形式计算区间和进而有sum[i]-sum[q.front()]这一重要的步骤，而为了使答案最大化我们需要时减数最小化，所以sum[q.back()]如果遇到了更小的sum[i]那么这个队尾就会被淘汰新的队尾更加合适。
所以简而言之对于单调队列的题目我们需从其最值的计算方式入手，找到单调性关系（一般为队尾与新入队的数作比较）。
更正补充
对于我对单调队列的题目没有一个清晰完整的流程特来补充
1.俩个单调队列的题目都是首先我们发现了其是一个滑动窗口，然后题目要求某最值
2.我们把队首作为最小或最大状态进行保持单调性的后移动，按这种方法来很轻而易举的就能把模版题目做出来，但前缀和变式不行；
前缀和变式通过固定i在窗口内找到一个最小sum[j]使得sum[i]-sum[j]最大化，所以我们要维护的队列就变成了sum[j]的单调递增队列
)