【剑指offer】滑动窗口的最大值

【摘书上】
deque是一个双端队列，用来保存有可能是滑动窗口最大值数字的下标；
在存入一个数字的下标之前，首先要判断队列里已有数字是否小于待存入的数字，如果小于则以此从队列的尾部删除；
如果队列头部的数字已经从窗口滑出，那么滑出的数字也需要从队列的头部删除。

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public ArrayList<Integer> maxInWindows(int[] num, int size) {

        ArrayList<Integer> list = new ArrayList<Integer>();
        Deque<Integer> deque = new LinkedList<Integer>();
        if (num == null || size <= 0 || size > num.length) {
            return list;
        }

        for (int i = 0; i < num.length; i++) {

            while (!deque.isEmpty() && num[i] >= num[deque.peekLast()]) {
                deque.removeLast();
            }
            if (!deque.isEmpty() && i - deque.peekFirst() >= size) {
                deque.removeFirst();
            }
            deque.addLast(i);
            if (i >= size - 1) {
                list.add(num[deque.peekFirst()]);
            }
        }
        return list;
    }
}