【双端队列】【维护单调队列】Leetcode 239 滑动窗口最大值【难】

---------------🎈🎈题目链接 Leetcode 239 滑动窗口最大值🎈🎈-------------------

双端队列的操作

创建双端队列：Deque<Integer> mydeque = new Deque<>()
双端队列的队首元素：mydeque.peekFirst()
双端队列的队尾元素：mydeque.peekLast()
双端队列的队首元素弹出：mydeque.pollFirst()
双端队列的队尾元素弹出：mydeque.pollLast()
双端队列的队首元素加入：mydeque.addFirst()
双端队列的队尾元素加入：mydeque.addLast()

解法1 利用双端队列实现单调队列

首先，先从第一个滑动窗口开始维护一个单调队列：这里向队列内添加元素时，需要始终保证mydeque.peekLast() 大于 新添加的元素，即如果新添加的元素大于队列末尾的元素时，需要while弹出队列末尾元素（直到满足上述条件），之后再将新元素添加到队列末尾：mydeque.addLast(新元素)。
其次，在窗口开始滑动的时候，每次滑动后，需要验证当前队列中队首元素（也就是目前队列中的最大元素）是否是在滑动中需要被踢出队列的元素（比如当前队列中的-3 1 3 再次进行滑动后 ——按照原数组位置来看3会被踢出）：即判断mydeque.peekFirst() 是否等于 nums[i-k],若等于，则踢出队首元素后再进行第一步中的入队验证等一系列操作。
最后，从遍历的i>k-1开始，每次都要输出result[i-k+1] = mydeque.peekFirst() 即输出滑动窗口内的最大值至result数组。

时间复杂度O(N)：使用单调队列的时间复杂度是 O(n)
空间复杂度O(K) ：K就是自己维护的队列的长度

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> mydeque = new LinkedList<>();
        int[] result = new int[nums.length-k+1];

        int index = 0;
        for(int i = 0; i<nums.length; i++){
            // 弹出队列操作
            if(i > k-1 && mydeque.peekFirst() == nums[i-k]){
                mydeque.pollFirst();
            }

            // 入队列操作
            while(!mydeque.isEmpty() && mydeque.peekLast()<nums[i]){
                mydeque.pollLast();
            }
            mydeque.addLast(nums[i]);

            
            //得到队首值mydeque.peekFirst() 即为最大值
            if(i >= k-1){
                result[i-k+1] = mydeque.peekFirst();
            }
            
        }
        return result;
    }
}