算法笔记：单调队列

单调队列：

队列元素之间的关系具有单调性（从队首到队尾单调递增/递减），队首和队尾都可以进行入队出队（即插入删除）操作，本质是由双端队列deque实现。

适用问题

通常解决动态小区间中寻找极值问题。

239. 滑动窗口最大值

思路：

由于需要比较在一个窗口里面的最大值的问题，最暴力的解法就是每次都去遍历窗口中的元素，然后取极大值，但这种情况只要K稍微大一点性能便会很差，而单调队列可以只进行维护最大值的操作，来优化性能。在本题中，关键的就是一个窗口中最大值在下一次移动的留存问题需要注意，比如[4,2,1],k=2,时，首先窗口为[4,2]那么此时单调队列中的元素就为[2.4]，4在队首的位置，那么下一次移动窗口成为[2,1]由于4是上一个窗口的最大值，但也是边界元素，下一次移动就会需要剔除，而单调队列恰好可以做到，那么此时4会从队首弹出，那么队列中次大的2就到队首，那么就和新进来的元素1比对来取值。

单调队列是通过双端队列Deque对象来进行操作，即可以进行头尾操作。

流程是当一个队列入队时，从尾部不断弹出元素进行比较，如果元素比队列中的元素大，那么就将队列中的元素弹出，直到存放到不大于队列中的元素的后面，或者最前面。

一个很有意思的描述。

代码：

class Solution {

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

    public int[] maxSlidingWindow(int[] nums, int k) {
        
         //思路：单调队列
        //java中的API  Deque:双端队列 可以同时进行头尾操作
        //从队头进行出元素  队尾进元素
         Queue<Integer> result=new LinkedList<>(); //存放结果队列   
         
            if(k==1){
                int [] ex=new int[nums.length];
                for(int c=0;c<nums.length;c++){
                    ex[c]=nums[c];
                }
                return ex;
            }
        //先初始化 第一个窗口
        for(int x=0;x<k;x++){
            push(nums[x]); //调用入栈操作
        }
        result.offer(queue.peekFirst());
        pop(nums[0]); //判断左指针是否是最大值下标 不是则不用管

        //开始从第一个窗口后进行判断
         for(int left=1,right=k;right<nums.length;){
               //那么第二个窗口和第一个窗口的区别就是要 判断左指针的元素是否是当前窗口最大值 右指针的元素是否比当前窗口最大值大
               //先判断当前右指针 使右指针元素入队
                push(nums[right]);  
                //右指针入队后 查看队首的最大值
                result.offer(queue.peekFirst()); //将最大值存入结果队列
                //然后需要在移动指针前判断当前左指针是否是最大元素
                pop(nums[left]); //如果是就需要弹出队首元素

                left++; 
                right++;

         }

         Object [] r=new Object[result.size()];
         r=result.toArray();
         int [] R=new int[r.length];
          for(int y=0;y<R.length;y++){
                R[y]=Integer.parseInt(String.valueOf(r[y]));
            }

        queue.clear();
        return R;
    }

    public static void push(int x){ // 入队方法 需要从队尾去判断元素大小
        
        while(!queue.isEmpty()&&queue.peekLast()<x){  //队列首先不能为空 然后从队尾拿元素 如果目标值大于队尾元素 则将队尾元素弹出
            queue.pollLast(); //将所有小于目标值的队尾元素弹出
        }//所有元素已经弹出
        //然后将该元素放置队尾
        queue.offerLast(x);

        //这样做是因为 只需要维护一个滑动窗口中的最大值即可，其余元素不用维护 当滑动窗口变动时 只需要关注最大值的那个元素是否被移除
    }


    public static void pop(int y){
        //出队方法是当滑动窗口左指针移动时 需要判断移出去的那个左边的元素是否是最大值,如果是最大值就需要调用该方法 将单调队列中的最大值弹出
       if(!queue.isEmpty()&&y==queue.peekFirst()){
            queue.pollFirst();//弹出队首元素
       }
    } //出队方法  从队头出队拿元素


}