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

思路:
1.使用队列，队头保持是最大的值的下标
2.每次遍历时先将队列中，从尾到头，比当前小的值移除。此时队列要么是空的，要么还有个比当前数大的值
3.对队头的下标进行边界约束，如果在i - size 前，即index <= i - size，就说明在窗口外了，我们移除队头的数据
4.每次队列头部数据就是窗口最大的值
5.当然也可以用暴力解法，for循环遍历，每size个数比较一下

import java.util.*;
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<>();


        for (int i = 0; i < n; i++) {
            //1.队列中  队头都是大的数，队尾都是当前数
            while (!queue.isEmpty() && num[queue.peekLast()] < num[i]) {
                //队列中只保存比当前数大的数
                //从队尾开始，移除调比当前数小的数，因为比当前数小，那最大的数不就是当前数么
                queue.removeLast();
            }
            queue.addLast(i);
            
            //边界问题处理
            //当前队头是最大的数，不在窗口内需要移除
            //为什么需要移除？为什么会出现窗口外的数在里面？
            //因为你保存的是最大的数在队列中，如果第一位是10，后面都是比10小的，是不是遍历到最后一个窗口，不包含第一个数10的时候，
            //队头都还是最大值10，所以每次遍历的时候都移除一下
            if(queue.peekFirst() <= i - size){
                queue.removeFirst();
            }
            if( i >= size - 1){
                result.add(num[queue.peekFirst()]);
            }
        }
        return result;
    }
}