import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        if(size > num.length || size==0){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        for(int i=0;i<(num.length-size+1);++i){
            int maxValue = num[i];
            for(int j=1;j<size;++j){
                if(maxValue < num[i+j]){
                    maxValue = num[i+j]; 
                }
            }
            res.add(maxValue);
        }
        return res;
    }
}

方法一：暴力求解

遍历数组，遍历窗口两层循环实现，每次找到窗口中的最小值存入列表中。注意返回空是指返回空数组，而不是null。

方法二：双端队列

双端队列，就是可以在两端进行插入和删除的队列。为什么用双端队列呢？因为数组遍历时，每个元素都需要进队，进队前要把比它小的值移除，队列末尾就出现既需要插入有需要删除的操作，而队头又需要出队作为窗口最大值，所以用到双端队列。

1、判断特殊情况，窗口大于数组大小或者为0 的情况

2、定义数组列表存储每个窗口最大值，定义双端队列用于存储数组下标。

3、处理第一个窗口，只存最大值

4、遍历数组，先将最大值入数列，然后处理前先保证队列中的下标不能小于当前数组下标前的一个窗口长度的下标。

5、再处理后续窗口，先将比当前数组的值小的元素一个个移除，再将当前数组值的下标存入，循环第4和第5步.

6、最后数组元素遍历结束，最后一个窗口的最大值下标还在队列中，将其添加到数组列表中

记：

双端队列的常用函数结尾都加First或Last区分对尾部或者头部的操作，如：

队尾入队用addLast或add, 队尾出队用pollLast，获取队尾的值而不出队用peekLast。

队头入队用addFirst, 队头出队用pollFirst或poll，获取队头的值而不出队用peekFirst或peek。

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows (int[] num, int size) {
        if(size > num.length || size==0){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> res = new ArrayList<Integer>();
        //双端队列存储数组下标
        ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
        //先遍历一个窗口，得到目前的最大值
        for(int i=0;i<size;++i){
            while(!dq.isEmpty() && num[dq.peekLast()]< num[i]){
                dq.pollLast();//移走较小的值
            }
            dq.addLast(i);
        }
        for(int i=size;i<num.length;++i){
            res.add(num[dq.peekFirst()]); //窗口的最大值进数组列表
            //移除一个窗口长度之前的值
            while(!dq.isEmpty() && dq.peekFirst()<(i-size+1)){
                dq.pollFirst();
            }
            //新值入队，在此之前要先将比它小的值从尾部开始移除
            while(!dq.isEmpty()&&num[dq.peekLast()]<num[i]){
                dq.pollLast();
            }
            dq.addLast(i);
        }
        //数组元素遍历结束，最后一个窗口的最大值下标还在队列中，将其添加到数组列表中
        res.add(num[dq.pollFirst()]);
        return res;
    }
}