单调队列

一句话理解

单调队列：队列里下标递增、值单调。

为什么要学

滑动窗口最值 O(n)。

讲解

新来的把尾部更差的挤走。队头过期就弹。队头就是当前最优。

例子

窗口最大值：维护递减队列，队头最大。

常见错误

• 只按值弹不按过期弹。
• 存值不存下标导致无法判断过期。