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

public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        //暴力解法 n - size + 1个窗口 每次都遍历循环
        //获取用队列
        if(num == null || num.length == 0 || size < 1 || num.length < size){
            return new ArrayList<Integer>();
        }
        ArrayList<Integer> result = new ArrayList<>();
        int n = num.length;
        Deque<Integer> queue = new LinkedList<>();
        
        //先将size数据放入队列中，然后取出最大值，然后将窗口第一个数移除，窗口后移
        //这里并没有这样做，
        //队列存的从对头到队尾都是最大到最小排列
        //每次往队列存值时，都会从队列列末尾比较，值小的就直接出队 这样当前的最大值就出来了
        //然后每次遍历是，在下标是 size - 1 到 n -1 每次都peekFirst 最大值就好了
       
        for(int i = 0;i< n;i++){
            while(!queue.isEmpty() && num[queue.peekLast()] < num[i]){
                //队列中 从队尾开始 只要比当前数小 移除
                queue.removeLast();
            }
            queue.addLast(i);
            // 每次遍历的时候，如果存放的值 不在 窗口里，需要移除
            if(queue.peekFirst() <= i -size){
                queue.removeFirst();
            }
            //窗口从 size - 1 到 n - 1
            if(i >= size - 1){
                result.add(num[queue.peekFirst()]);
            }
        }
        return result;
    }
}