其实是个比较简单的数据结构了，引用百度百科给出的说明，其对应的问题是：不断地向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;
}
下载文件 (已下载 次)