单调队列及 dp 优化

_Cheems · 2023-08-15 21:34:26 · 个人记录

单调队列

• 定义及性质

  满足队内元素值单调递增或递减、元素下标单调递增或递减的一个队列，统称为单调队列

• 实现

  假如要在队尾新插入一个元素，为了维护单调性，需将不断删除队尾元素，直到插入后满足单调性再插入，关键在于这样做为何是对的。

  这里描述值单调递增、下标单调递减的单调队列。

  其实就是利用了决策单调性，若满足 a_i\le a_j 且 i>j，则选 i 一定优于选 j。

  从元素值来看，若有区间 [l,r] 包括了 a_i,a_j，那么要取也一定取 a_i 而不是 a_j；从下标来看，显然不存在区间 [l,r],r\ge i 使得其取不到 a_i 却可以取到 a_j。而对于区间 [l,r],r<i，那么自然不会用 a_i 淘汰掉 a_j。因此正确性得证。

  所以单调队列可用于求静态区间最大最小值，且由于每个 a_i 会且仅会被入队、出队一次，所以时间复杂度是线性的。

  咕咕咕~