单调队列

之前听松爷扯过单调队列,于是学了一番,感受是这样的:
妙啊
单调队列大法好,$O(n \log n)$$O(n)$

性质

单调队列,顾名思义,是一个“单调”的队列。
如何便是单调?单调递增/递减。假设下面说的都是单调递减队列。

插入元素时,如何维护单调队列的单调性? 这是单调队列中最基础的问题。
解决方法往往很粗暴:先把队尾所有小于插入元素的都删除,然后插入元素。 这样就有序了。但是有个问题,为什么可以直接删除那些元素?

与要维护的东西的性质有关。

显然,我是懒得手打循环队列的。上STL大法——双端队列

#include <deque>
using namespace std;

int main()
{
    deque <int> q;
    q.push_front(1);             //队首插入1
    printf("%d\n",q[0]);         //滋磁随机访问!
    q.push_back(2);              //队尾插入2
    q.push_back(3);              //队尾插入3
    q.pop_back();                //弹出队尾元素
}

例题:滑动窗口

一个长度为$n$的序列,有一个长度为$k$窗口在其中滑动。 求出:每一个位置,窗口中元素的最大值、最小值

Example:

窗口位置                 最小值    最大值 
[ 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 

暴力

想题先想暴力?

对于每个窗口位置,暴力求最大最小值。 复杂度$O(n*k)$

平衡树

考虑优化上面的暴力。 根据滑动窗口的性质,每次移动只有一个元素进入、一个元素弹出。

由此,维护一个平衡树,储存元素的出现次数。取最大/最小值输出,窗口移动时删除左边元素、加入右边元素。

可以用STL的multiset(可重复集合)来处理。 复杂度$O(n \log n)$

单调队列

首先,我们只考虑最大值。最小值是类似的。窗口在移动,我们需要维护窗口中的最大值。

考虑下面的事实:如果有$l<i<j<r$,则如果$a_i$可选,那么$a_j$也可选。
这是很显然的。窗口在向右移动,$a_i$$a_j$的左边,因此$a_i$$a_j$先弹出窗口。

继续思考,如果$a_i<a_j$,因为在$a_i$可选的情况下$a_j$可选,所以一定不会选择较小值$a_i$。可以直接删除$a_i$

那么容易想到用单调递减队列维护最大值。做法: 1. 查询。直接输出队首元素。 2. 插入右端点。根据刚才想到的性质,弹出所有小于右端点的元素,然后把右端点加入。

最棘手的问题,如何删除左端点?
我们知道如何删除堆中的元素:另建一个堆,将准备删除的元素放进删除堆;如果删除堆和原堆的堆顶相同,则各自弹出堆顶。
上面的方法的思想是,不去直接找到元素删除,而是当那个元素准备使用时删除。

推广到这个单调队列上。容易想到:有用的元素一定在$[l,r]$
因此,处理队首元素时,当队首元素在$[l,r]$之外,直接弹出它,直到队首元素在$[l,r]$内为止。

如何计算复杂度?每个元素入队一次、出队一次,因此处理每一个元素的复杂度是$O(1)$,总复杂度是$O(n)$


CC0协议 @ ruanxingzhi 2017. CC0是啥玩意?
Home apps close