【模板】单调队列

题目

洛谷P1886滑动窗口

题解

单调队列通常用来求序列中具有长度上限的区间信息的最值。将序列从左往右扫描,维护一个双端队列,队列中的元素具有广义单调性(如果新元素在数值上优于老元素,则可替代它;如果新元素在数值上等于老元素,则新元素更容易作为接下来某区间的元素,所以也可替代它),在数值上越优,加入时间越晚的元素具有更高的优先级。容易发现队列中的元素有这样的性质:从队头到队尾,元素在数值上递减,在加入时间(下标)上递增。每次遇到一个新元素,先用以它与队头为端点的区间信息更新答案,然后将此元素加入队列,同时维护队列性质。在此算法中,每个元素入队一次,出队一次,时间复杂度为O(n)。

代码

Subscribe
提醒
guest
3 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年9月3日 下午4:12

【小白解析】
理解题解需要明确两个数组和数个相关变量的意义:
l:左端指针;
r:右端指针;
第9&21行的i:当前考察范围最右端的下标#
q[x]:以x为最左端的区间[x,x+k-1]#中,最小/最大值的下标;
从get_min()函数入手。第11行的while循环考察两个状态:前者是考察用的左指针不大于右指针,后者q[l]<=ik(当q[l]==i-k+1时终止循环)保证现有的最小值下标q[l]不小于当前考察范围的最左端i-k+1(即找到[i-k,i]内的最小值),用作此题答案。
第12行寻找后续循环中可能使用的最小值。同样先保证左指针不大于右指针,随后考察[r,r+k-1]范围内的最小值是否小于a[i]。当找到第一个a[i]>a[q[r]]时,说明a[i]在当前的[r+1,r+k]范围内是最小值,故将其赋值给q[r+1](即q[++r])。
因为每次循环i必加一,r增幅不超过1且可以小于0,而初始时r==0,i==1,故i一定不在r的左侧,r作为考察范围的最左端有效。奇妙的是,l在第一次循环内一定满足q[l]>=i-k+1,致使每一次for()循环结束时,r>=i-k+1,随后r++,保证下一局即便l<=r判断不成立,l==r+1时依旧小于当前的i-k+1(i和r各自+1),故不必担心判断失误。#
最后,考察当前范围的最右端是否大于k-1#(即是否能构成长度为k的窗口)。如果能,输出答案。
get_max()函数实则是改变了第二个while()的判断条件,其基本思路与get_min()一致。
*此解析可能存在问题,存疑点均用#标出,请各路大神做详尽解析。

cyx
cyx
Reply to  Martin
2020年9月3日 下午8:11


看样子正确的思路应该是

  1. 截取目前区间内的最小值q[l],区间[q[l],i]的长度不大于k;
  2. 考察新读入的数据a[i],从a[i-1](由于上个循环中q[++r]=i,随后i++)开始搜寻对应a[]值单调递减的数组q[]内第一个小于a[i]的数字的下标,替换其为a[i]的下标;

*没关系的,都一木羊——(负隅顽抗)