单调队列

compaq · 2025-03-18 15:52:35 · 算法·理论

定义

顾名思义，单调队列的重点分为「单调」和「队列」。

• 「单调」指的是元素的「规律」——递增（或递减）。
• 「队列」指的是元素只能从队头和队尾进行操作。 Ps. 单调队列中的 "队列" 与正常的队列有一定的区别，稍后会提到

简单来说，分成两个操作：

• 1：删除冗余数据
• 2：维护队列长度

应用：

P1886 滑动窗口 /【模板】单调队列

滑动窗口是一类问题，需要在一个长度为n的序列中，找到所有长度为k的连续子序列中的最大值或最小值。使用单调队列可以在O(n)的时间复杂度内解决该问题。

具体做法如下：

• 1.首先，将前k个元素插入单调队列中，并记录队列的最大值或最小值。
• 2.然后，从第k+1个元素开始，每次将一个新的元素插入单调队列中。
• 3.插入时，先将队列中所有小于等于该元素的队尾元素出队，保证队列中的元素单调递减。
• 4.然后，将该元素插入队尾，并记录队列的最大值或最小值。
• 5.最后，将长度为k的子序列的最大值或最小值输出即可。