标题：补缺补漏：单调队列
出处：Felix021
时间：Fri, 10 Dec 2010 15:35:46 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1965

内容：
其实是个比较简单的数据结构了，引用百度百科给出的说明，其对应的问题是：不断地向buffer里读入元素，也不时地去掉最老的元素（ buffer 的大小取决于移除最老元素的策略，可以是不定长的；下文假定是固定为K的），不定期的询问当前buffer里的最小的元素。

使用普通队列来实现，每个元素O(1)的操作，每次查询O(K)；用堆实现的话，每次查询是O(1)，但是每个元素是O(logK)。还有其他的实现方式，比如线段树，或者RMQ，这些都是logN量级的。

而单调队列的优势则是，每个元素是O(1)的操作，又能保证最小元素像堆一样在最前面，也就是每次查询O(1)。具体的实现也非常简单，不过它并不是通常意义上理解的队列。

以此为例：对于N=8，K=3，8个元素序列1 3 -1 -3 5 3 6 7，窗口大小为3，也就是要求出(1, 3, -1), (3, -1, -3), (-1, -3, 5), (-3, 5, 3), (5, 3, 6), (3, 6, 7)这6个序列中的最小值，结果简单，就是-1, -3, -3, -3, 3, 3. 

使用单调队列，首先要有一个数据结构struct node { int seq, val; }
用于记录队列中的元素及其在输入序列中的顺序。队列的状态是这样维护的：

 1: [0,  1] //队列空，[seq=0, val=1]入队
 3: [0,  1], [1,  3] //3大于队尾元素，放在队尾
-1: [2, -1] //从队尾往前扫，-1小于每一个所有元素，于是把它们都T掉
-3: [3, -3] //-3把-1T掉
 5: [3, -3], [4,  5] //入队尾
 3: [3, -3], [5,  3] //把队尾的5T掉
 6:            [5,  3], [6,  6] //队首元素seq=3太老了，T掉；6比3小，放在队尾
 7: [5,  3], [6,  6], [7,  7] //入队尾

从以上的处理方法可以看出：最老的元素要么早就被T掉了，要么就是最小的元素（排在队首）。所以每次加入一个新元素的时候:
1. 把需要出队的队首元素T掉；
2. 把队尾大于或等于它的元素全部T掉，自己入队。

POJ2823 http://poj.org/problem?id=2823 是一道适合用单调队列来求解的题目，效率会特别高；不过一定要注意，由于WS的POJ会卡IO时间，所以需要自己实现一份read_int()和print_int()来替换掉scanf和printf。

最后，附上一份简单的单调队列代码：#include<stdio.h>

int main() {
    struct node {
        int seq, val;
    } q[100]; //q: queue
    int N, k, i, f, b, t, ans[100];
    scanf("%d%d", &N, &k); //不是内裤
    f = b = 0; //f: front, b: back
    for (i = 0; i < N; i++) {
        scanf("%d", &t);
        if (f < b && q[f].seq <= i - k)
            f++; //把需要出队的队首元素T掉
        while (f < b && q[b-1].val >= t)
            b--; //把队尾不大于t的元素T掉(注意等号!)
        q[b].seq = i, q[b].val = t, b++; //入队尾
        ans[i] = q[f].val; //保存当前的最小值
    }
    for (i = k - 1; i < N; i++)
        printf("%d ", ans[i]);
    return 0;
}



Generated by Bo-blog 2.1.0