【剑指 Offer】59 - I. 滑动窗口的最大值(详细解析)

题目链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

1. 双向队列

   解题思路：

   第一时间想到的是暴力破解，但是暴力破解肯定没前途啊，后面又思考了很久~~

   使用双向队列，来存放窗口中的值，并且时刻保证队列中最左端为窗口数的最大值；

   如何实现？：窗口每次向右移动，添加数值到队尾并且将队尾左侧小于该数值的数移除。

   这样就保证了，队列头时刻为窗口里的最大值！！

   但有些细节要注意，如果窗口为2，数组为5,1,2,3,4；这样的按上面算法，5在队列中一直不会过期。

   所以要设立一个窗口的左指针，移动后判断左指针的数是否和队列头的数相等，相等就设置过期。

   详细代码如下：

   class Solution {
       public int[] maxSlidingWindow(int[] nums, int k) {
           if (k==0||k==1) return nums;
           Deque deque = new linkedList<>();
           int[] res=new int[nums.length-k+1];
           int l=1-k,r=0;
           //形成窗口期
           for (;rdeque.getLast())
                   deque.removeLast();
               deque.add(nums[r]);
           }
           res[l-1]=deque.getFirst();
           //已形成
           for (;rdeque.getLast())
                   deque.removeLast();
               deque.add(nums[r]);
               res[l]=deque.getFirst();
           }
           return res;
       }
   }