单调队列的性质
- 单调队列中的元素单调递减或单调递增
- 只能在队尾插入，可以从两头删除
其目的就是为了保持队列中元素的单调性，从而满足动态规划的最优性问题的需求。
从一个例子理解单调队列及其应用
问题定义
给定一个长度为N的整数数列a1,... ,aN,i=0,1,...,N-1和滑动窗的长度k. 求窗里面所包含的数的最大值。
思路1，暴力破解法
从数列头部开始，每次移动滑动窗一次，每移动一次，便求出该窗口内的最大数。显然时间复杂度O(kN)
思路2，单调队列优化
显然，思路1 的方法的缺点在于每一次求滑动窗里面的最大数，都重复比较了滑动窗里面的前k-1数。
因此，我们可以保存滑动窗里面的前k-1数中的最大值，每次移动滑动窗时，更新这个最大值。
更新方法:
假设滑动窗口大小k=3, 数列为：8, 7, 12，5，16，9，17，2，4，6
滑动窗在数组的某个位置上: [8, 7, 12]，5，16，9，17，2，4，6 (方括号表示滑动窗)
q={(8, 0), (7,1)} (窗口中前2个元素的最大值及其在原始数组中的位置)
移动滑动窗口:8, [7, 12，5]，16，9，17，2，4，6 (方括号表示滑动窗)
队列q中的队首元素，如果已经不在窗口中，需要删除。q={(7,1)}
向队列尾部插入元素 12, 为保证队列的单调性，从队列尾部开始，删除队列中比12小的数，然后插入12。q={(12,2)}
移动滑动窗口:8, 7, [12，5，16]，9，17，2，4，6 (方括号表示滑动窗)
队列q中的队首元素，如果已经不在窗口中，需要删除。
向队列尾部插入元素 5, 为保证队列的单调性，从队列尾部开始，删除队列中比5小的数，然后插入5。q={(12,2), (5,3)}
......
如此循环，直到队列尾部, 就求出了每个窗口中的最大数.
解 res[i] 就是 第 i 步 队列中的首元素
/**
*
* @param A
* @param k 滑动窗口大小;
* @return 滑动窗的中最大数
*/
public int[] calcMaxNumInSlidingWindow(int[] A, int k){
Deque<Pair> q = new ArrayDeque<>();
int[] res = new int[A.length - k + 1];
int curMax = Integer.MIN_VALUE;
for(int i=0, cnt=0; i<A.length; cnt++, i++){
// 更新q
while(q.peekLast().val < A[i]) q.pollLast();
q.offerLast(new Pair(i, A[i]));
while(!q.isEmpty() && q.peekFirst().idx < i-k+1)
q.pollFirst();
if(i >= k-1){
res[i-k+1] = q.peekFirst().val;
}
}
}
参考文献：
http://blog.csdn.net/hackbuteer1/article/details/7424466
http://blog.csdn.net/justmeh/article/details/5844650
