很早看过这个东西，不过今天遇到一道题发现居然没有写笔记。。。这里补上吧。

以下是我从某个题的解题报告翻出来的。转载的别人的。。。。

以此为例：对于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掉，自己入队。

 

说白了就是是保证窗口的元素的value是从前往后是依次减小(增大)的。还有一个值就是当前value的position，也就是说窗口里所有元素 的position都必须跟当前待插入的元素的position的距离相差小于等于窗口的大小。（-_-! 说的好别扭）

 

今天补补模板吧。。。。

class Node {public:    int pos;    int val;    Node() {};    Node(int _a, int _b) : pos(_a), val(_b) {}};class Dequ{    Node deq[N];public:    void Get_Min(int ans[], int _num[], int n, int k) {        int i, head, tail;        head = tail = 0;        REP(i, n) {            if(head < tail && deq[head].pos <= i - k)   head++;            while(head < tail && deq[tail-1].val >= _num[i])    tail--;            deq[tail++] = Node(i, _num[i]);            ans[i] = deq[head].val;        }    }    void Get_Max(int ans[], int _num[], int n, int k) {        int i, head, tail;        head = tail = 0;        REP(i, n) {            if(head < tail && deq[head].pos <= i - k)   head++;            while(head < tail && deq[tail-1].val <= _num[i])    tail--;            deq[tail++] = Node(i, _num[i]);            ans[i] = deq[head].val;        }    }} Dequeue;