Zth's Blog

记录学习路上的点滴

0%

浅谈单调队列优化

记录自己对单调数据结构的理解

单调栈

单调栈无需多言, 就是在一个线性序列中找到当前元素前面/后面第一个大于/小于该元素的元素, 代码实现也很简单

单调队列

什么是单调队列

在一个线性序列中通过贪心思想维护一个有序的队列, 方便我们查询想要的信息(通常是极值或者前驱后继)

适用单调队列的情况

在一个线性序列中, 我们需要对每个元素都执行下列两种操作的一种(注意是一种操作对应所有元素(不过好像同时存在两种也能做啊, 开两个单调队列就是了)), 不失一般性的, 我们假定从前往后遍历

  1. 查询前边的元素中第一个比该元素大/小的元素
  2. 查询前边元素中最大的一个元素

但是这个上述两种查询通常都是限定了范围的(显式的或隐式的, 否则第一种操作就和单调栈一样了, 第二种操作前缀就可以了), 这样我们就需要通过弹出队头来维护范围, 舍弃那些超出范围的元素; 通过弹出队尾来维护队列的单调性

下面简单列举一下几种常见的情况

显式的, 如$f[i] = \mathop{max}\limits_{i - k \leq j \leq i} \{f[j] + x[i]\}$

这种情况下范围直接给定了, 我们使用一个双端队列, 队头弹出意味着队头元素的范围失效; 队尾弹出发生于维护队列的单调性

隐式的, 维护第一个大于/小于该元素的元素(或者和该元素的差值的绝对值大于某个数的第一个元素)

这种情况可以参照我的一篇题解测温(这题我是从后往前遍历的)

在本题中, 我们利用单调栈的思路先找到后边第一个小于该元素(设位置为$i$)的元素的位置$pos$,那么我们就得到 了$ans[i] = pos - i$

然后我们就需要维护单调队列了, 对于这个题而言, 我们弹出队头是在维护队列的单调性; 此外我们需要弹出队尾, 也就是队列中$pos$及其之后的元素, 因为我们从当前元素无法到达它们, 而$i$前面的元素必须通过$i$才能到达它们, 所以它们不可能被到达, 应该直接删掉, 可以理解为范围的限制, 这些元素范围的失效了

这种情况说白了就是带删除范围失效元素的单调栈, 算是单调栈的扩展

隐式的, 维护极值

本来想放这个题的题目链接

就是给一个二维的矩阵, $n$是$500$, 找一个最大的子矩形, 它里边的最大值最小值之差不超过给定的$m$, 使这个子矩形最大(包含最多的元素)

正解是枚举答案矩形的上下界, 然后枚举右边界, 单调队列维护左边界

看到有题解说是维护极值, 但我想了想其实不是,这应该还是是上边的第二种情况, 只不过第一个大于和小于(差的绝对值)的位置一块维护罢了

所以这个题应该归结于第二种情况, 但是说是极值应该也没有错, 确实是按照极值来维护的, 我们找的也是符合条件的最大/最小值, 所以放到这里吧

第二种和第三种可能是同一种情况吗所以(合理, 因为序列有序, 两者其实是一样的, 可以理解为“符合限定条件的极值”), 还是说第三种情况就不存在(也合理, 因为找到的极值必然是队头啊, 也就没有什么可删的了)