滑动窗口的最大值【Java版】

【总体思路】采用 双端队列ArrayDeque，两端巧妙删除/增加；达到O(N)时间。

import java.util.ArrayList;
import java.util.ArrayDeque;
//ArrayList有index->value的对应，而ArrayDeque只有值，没有下标，无法随机查找，只能操作两头，但两头高效。
//ArrayDeque类型,双端队列。（只有两头可以读写，中间不能读写查）

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        ArrayDeque<Integer> qmax = new ArrayDeque<Integer>(size);//qmax用于存序号i,而不是存num[i]里面的值。
        if(num==null || num.length < size || size<=0)return res;//不能是return null
        for(int i=0; i<=num.length-1; ++i){
            //1.右入qmax
            while(qmax.peekLast()!=null && num[i] > num[qmax.peekLast()])qmax.removeLast();
            //【冒泡排序思想】qmax里面的值，左大右小。//去除num[i]左边相邻连续一排较小值。(新比旧大，旧必无用)
            qmax.addLast(i);//最右边一格，而不一定和原先的连着??
            //2.左出qmax
            if(qmax.peekFirst() == i-size) qmax.removeFirst();//左框最左才会出  //不是 ==i-size+1
            //3.res收当前max
            if(i>=size-1) res.add(num[qmax.peekFirst()]);//最左边一定是当前的最大值，进入结果数组
        }
        return res;
    }
}//时间O(N)  空间O(N)
//最粗犷的方法是O(N*size)
//因为有while循环，单轮最多O(size)。但整体平均每轮<=O(1)，因为数字不够每轮都O(size)规模删除