单调队列学习笔记 | Menci's Blog

单调队列学习笔记 | Menci's Blog

单调队列，就是单调的队列，通常用来解决滑动窗口的最值问题，可以应用到 DP 的优化上。一个单调队列中的元素总是单调递增（或递减）的。

滑动窗口

例：有一个队列，每次从队尾加入一个元素，或从队首删除一个元素，并在任何时刻求整个队列的最大值。

一个很直接的想法是使用优先队列 priority_queue 即堆，堆可以在 $O(1)$ 的时间内求出最大值，但每次加入或删除时需要 $O({\log}n)$ 的时间完成堆的调整，但是用了堆后就不能按照进队的顺序出队了！这时候你可以大胆地写一个平衡树或者 set——如果你不怕多出来的 $\log$ 和平衡树常数带来的 TLE 的话。

单调队列就是解决这类问题的数据结构，我们用一个辅助队列，使该队列的首元素总是原队列的最大值，这样就可以 $O(1)$ 地求出队列的最大值了。

Read full article from 单调队列学习笔记 | Menci's Blog