题解 | #滑动窗口的最大值#

思路：简单的暴力求解过程，通过Arrays.copyOfRange(num,i,i+size)来获取窗口，进行遍历求解

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer>list=new ArrayList<>();
        if (size==0){
            return list;
        }
        List<Integer>h = new ArrayList<>();
        for (int i=0;i<num.length;i++){
            h.add(num[i]);
        }
        for (int i=0;i<=num.length-size;i++){
            int a=sum(Arrays.copyOfRange(num,i,i+size));
            list.add(a);
        }
        return list;
    }
    private static int sum(int[] copyOfRange) {
        int sum=0;
        for (int i=0;i<copyOfRange.length;i++){
            if (copyOfRange[i]>sum)
                sum=copyOfRange[i];
        }
        return sum;
    }
}

思路2：采用滑动的思想，每次滑动size格就记下最大值，在向后退size-1格。 注意：

1、每次循环完毕max赋值要赋值下一个滑动的第一个位置的值（num[i-size+2]） 2、i值在滑动完以后要回到i-size+2的位置，因为for循环最后执行i++,所以赋值i=i-size+1

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer>list=new ArrayList<>();
        if (size==0||num==null){
            return list;
        }
        int max=num[0];
        int h=0;
        for (int i=0;i<num.length;i++){
            h++;
            if (max<num[i]){
                max=num[i];
            }
            if (h%size==0){
                list.add(max);
                h=0;
                int f=i-size+2;
                i=i-size+1;
                if (f==num.length){
                    f=num.length-1;
                }
                max=num[f];
            }
        }
        return list;
    }
}

思路三：使用双向队列进行计算

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
         ArrayList<Integer>list=new ArrayList<>();
        if (size==0||num==null){
            return list;
        }
        int begin;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int i=0;i<num.length;i++){
            //将size的数据放入双向队列中
            begin=i-size+1;

            //判断当前最大值是否过期
            if (q.isEmpty()){
                q.add(i);
            }else if (begin>q.peekFirst())
                q.pollFirst();

            //新增加的值从队尾比较，比它小的去掉
            while (!q.isEmpty()&&num[q.peekLast()]<=num[i])
                q.pollLast();

            q.add(i);
            if (begin>=0){
                list.add(num[q.peekFirst()]);
            }
        }
        return list;
    }
}