//Deque双端队列

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;

        int[] res = new int[len - k + 1];

        //或Deque

        LinkedList<Integer> queue = new LinkedList<>();

        for(int i = 0; i < len; i++) {

            //当最后的元素小于数组当前元素，弹出最后的元素

            while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]) {

                queue.pollLast();

            }

            queue.addLast(i);

            //当最前面的位置不在k个元素的范围时，从前面出队

            //小于i-k时

            if(queue.peekFirst() <= i - k) {

                queue.pollFirst();

            }

            //当元素达到k个时，将队头元素加入数组

            if(i - k + 1 >= 0) {

                //加入时不出队

                res[i - k + 1] = nums[queue.peekFirst()];

            }

        }

        return res;

    }

}

class Solution {

    /**

        注意尾部头部什么时候移除、结果添加

        2循环1判断

     */

    public int[] maxSlidingWindow(int[] nums, int k) {

        int len = nums.length;

        Deque<Integer> queue = new LinkedList<>();

        int[] res = new int[len - k + 1];

        for(int i = 0; i < len; i++) {

            //元素移除

            while(!queue.isEmpty() &&  nums[i] >= nums[queue.peekLast()]) {

                queue.pollLast();

            }

            //添加元素的函数

            queue.offer(i);

            //移除头元素，while，当头的位置不在k个区间时

            while(queue.peekFirst() <= i - k) {

                queue.pollFirst();

            }

            //添加元素到res，if，当窗口长度达到k个时，☆☆☆☆

            if(i - k + 1 >= 0) {

                res[i - k + 1] = nums[queue.peekFirst()];

            }

        }

        return res;

    }

}