单调队列

问题描述：

给定一个长度为N的整数数列{ai}，i = 0, 1, ... , N-1和窗口长度k.

要求：

　　f(i) = max{a(i-k+1), a(i-k+2), ... , a(i)}, i = 0, 1, ... , N-1.

解法：

　　在求f(i)时，其前k+1个数在f(i-1)中比较过，可以使用单调队列解决.

　　单调队列的头元素一直是队列中最大的，而且队列中的值是按照递减的顺序排列的. 允许从队列的末尾插入一个元素，从队列的两端删除元素.

　　1. 插入元素：为了保证队列的递减性，在插入元素v的时候，要将队尾的元素和v比较，如果队尾的元素不大于v，则删除队尾的元素，然后继续将新的队尾元素与v比较，直到队尾的元素大于v，并把v插入队尾。

　　2. 删除队首元素：队首元素的下标小于i-k+1.

Reference:

[1] http://blog.csdn.net/justmeh/article/details/5844650