单调队列这一字眼进一步理解明显的单调性基于近期复刷的单调队列题目形如经典的模版题目P1886 【模板】单调队列 / 滑动窗口 以及对此进行的变式P1714 切蛋糕 ,P1638 逛画展P1886的模版题让我重新回顾了一下如何维护一个单调区间在这道题中维护单调区间的意义是为了保持其当前窗口的最大值为队首队首则是依次为更小的值这样的区间有一个特点如果当我们队首因为离开了窗口内范围而跳脱此时新队首会成为新的最大而当我们窗口进行移动时如果新来的值的大小有点大我们就依次对队尾元素进行比较后让他们pop()毕竟他们这么小已经没有可能作为当前窗口的最大值了。我们找每个时期的最小值也是同样的道理。这样的题目常用双端队列deque进行解答对于我这种初学者来说单调队列的队列一词感觉有所误导因为初学者对队列的印象大都停留在先进先出的效果单调区间更感觉符合我们想要的效果感觉有点抽象。单调队列单调栈滑动窗口int n,k; cin n k; vectorinta(n1); vectorintans_mx; vectorintans_mi; dequeintmx; dequeintmi; for(int i1;in;i) { cin a[i]; } for(int i1;in;i) { while(!mx.empty()i-kmx.front()) { mx.pop_front(); } while(!mx.empty()a[mx.back()]a[i]) { mx.pop_back(); } while(!mi.empty()i-kmi.front()) { mi.pop_front(); } while(!mi.empty()a[mi.back()]a[i]) { mi.pop_back(); } mx.push_back(i); mi.push_back(i); if(ik) { 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; vectorinta(n1); vectorintsum(n1,0); dequeintq; for(int i1;in;i) { cin a[i]; sum[i]sum[i-1]a[i]; } q.push_back(0); int ans-LLONG_MAX; for(int i1;in;i) { while(!q.empty()i-mq.front()) { q.pop_front(); } ansmax(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; vectorinta(n1); vectorintnum(m1,0); dequeintq; for(int i1;in;i) { cin a[i]; } int k0; int ansLLONG_MAX; int l1,rn; for(int i1;in;i) { q.push_back(i); num[a[i]]; if(num[a[i]]1)k; while(!q.empty()km) { if(ansq.size()) { lq.front(); rq.back(); ansq.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]的单调递增队列
