Dec 10

补缺补漏:单调队列 不指定

felix021 @ 2010-12-10 15:35 [IT » 程序设计] 评论(4) , 引用(0) , 阅读(9578) | Via 本站原创 | |
其实是个比较简单的数据结构了,引用百度百科给出的说明,其对应的问题是:不断地向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;
}




欢迎扫码关注:




转载请注明出自 ,如是转载文则注明原出处,谢谢:)
RSS订阅地址: https://www.felix021.com/blog/feed.php
cotton
2011-2-2 13:38
很不错啊,对我这个菜鸟来讲帮助很大。祝RP春节一起++
crazyhadoop
2010-12-16 12:32
哇唔~这个自己read_int() 咋实现啊?
felix021 回复于 2010-12-16 16:07
就是一个将字符串解析成int的函数 很容易的吧
luoxi0209
2010-12-11 23:18
需要自己实现一份read_int()和print_int()来替换掉scanf和printf。不需要吧,我看了下以前写的代码。就是直接scanf和printf。
copper fittings Email Homepage
2010-12-11 16:48
代码看上去挺麻烦的,看不懂
felix021 回复于 2010-12-11 17:08
就20行……
分页: 1/1 第一页 1 最后页
发表评论
表情
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
emotemotemotemotemot
打开HTML
打开UBB
打开表情
隐藏
记住我
昵称   密码   *非必须
网址   电邮   [注册]