单调队列
单调队列最经典的应用就是 求滑动窗口中的最大值/最小值。
滑动窗口示意图:对于数组 [1, 3, -1, -3, 5, 3, 6, 7]
,窗口大小为 3
窗口位置 | 最小值 | 最大值 |
---|---|---|
[1 3 -1] -3 5 3 6 7 | -1 | 3 |
1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
1 3 -1 -3 5 [3 6 7] | 3 | 7 |
滑动窗口显然可以用队列来维护:
- 把新加入的元素加入队尾
- 从队头弹出最后一个元素
- 暴力做法就是每次循环判断队列中是否有重复元素,时间复杂度
依旧是考虑是否存在 逆序对:
例如:当 -3
加入滑动窗口后,-3
之前的 1, 3, -1
都不会成为最小值了。
删除所有这种逆序对后,得到的就是一个 严格单调上升的队列,该队列的最小值就是队列的队头。
算法流程:
- 对于这样一个单调队列,我们思考其维护过程
- 对于新元素
a[i]
,将其和 队尾元素a[j]
依次比较- 如果
a[i] <= a[j]
,弹出队尾元素,重复上述操作 - 如果
a[i] > a[j]
,直接加入队尾,此时队列保持严格单调上升
- 如果
- 由于窗口是滑动的,因此会有自然出队的情况
- 队列中改存 元素对应的下标
- 当新元素
a[i]
准备入队时,先判断此时的队头元素需不需要自然出队:if (i - q[hh] >= k)
- 队头元素自然出队后,再进行比较和新元素入队操作
核心代码:注意防止越界,先判断队列非空再取队头/尾
cpp
//...
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++) {
// end point: i, start point: i - k + 1
if (hh <= tt && q[hh] < i - k + 1) {
hh ++;
}
while (hh <= tt && a[q[tt]] >= a[i]) {
tt --;
}
q[++ tt] = i;
if (i >= k - 1) {
cout << a[q[hh]] << " ";
}
}
注意要先加入 i
,即 q[++ tt] = i;
,因为新加入的 a[i]
可能就是最小值。
显然,队头队尾都有弹出,这是一个 双端队列。