给出一个可能包含重复的整数数组，和一个大小为 k 的滑动窗口, 从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值。

题目链接

样例 1:

输入: [1,2,7,7,8] 3 输出: [7,7,8]  解释： 最开始，窗口的状态如下：`[|1, 2 ,7| ,7 , 8]`, 最大值为 `7`; 然后窗口向右移动一位：`[1, |2, 7, 7|, 8]`, 最大值为 `7`; 最后窗口再向右移动一位：`[1, 2, |7, 7, 8|]`, 最大值为 `8`. 

样例 2:

输入: [1,2,3,1,2,3] 5 输出: [3,3]  解释: 最开始，窗口的状态如下： `[|1,2,3,1,2 | ,3]` , 最大值为`3`; 然后窗口向右移动一位.`[1, |2,3,1,2,3]`, 最大值为 `3`; 

算法：单调队列

• 单调队列中的元素是严格单调的。我们在求解这个问题的时候需要维护他的单调性。
• 队首元素即为当前位置的最大值。假设要求滑动窗口中的最大值。我们就需要确保滑动窗口中的元素从队首到队尾是递减的。
• 每滑动一次就判断当前元素和队尾元素的关系，如果放入队尾满足单调递减，那么放入即可；如果放入不满足，就需要删除队尾元素直到放入当前元素之后满足队列单调递减。同时要确保已经出窗口的最大值（队首元素）被删除掉。

注意事项：

我们在本题中 往单调队列里压入的是元素对应的下标，因为我们要通过下标来判断该元素有没有离开了滑动窗口，如果离开了滑动窗口就得从队列里给删除了

流程

序列 a 是 1 2 7 7 6 5 3 滑动窗口的大小是 3 遍历一遍 for i in 0：7

• i==0 队列里没有元素，直接添加（ value=1,index=0 ） value 是权值，index 是下标（这里为了表达清晰，就把权值和下标都注明出来了） 队列里 (1,0)
• i==1 a[1]比队尾元素大，添加 a[1]后不满足单调递减性质，所以需要把队尾给弹出，a[1]比队尾大，而且队尾元素肯定在 a[1]的左面（因为队尾元素先压入的，它的下标肯定小），而且队尾元素还没 a[1]大，对于后面的窗口，队尾元素肯定不是最大值了（我们已经找到了 a[1]比，而且队尾在窗口里面，a[1]肯定也在窗口里面，因为 a[1]的下标更大）
  • 弹掉队尾后，队列为空
  • 压入(2,1)
  • 队列里 (2,1)
• i==2 a[2]比队尾元素大，弹掉队尾，压入(7,2) 队列里 (7,2) 这里 i>=k-1 了 ，当前队首为当前[0,2]这个滑动窗口的答案，这个窗口答案是 7
• i==3 a[3]不比队尾元素大，不用弹出队尾 ，压入新元素 队列里 (7,2) (7,3) 统计[1,3]滑动窗口的答案，也是 7
• i==4 a[4]不比队尾元素大，不用弹出队尾，压入新元素 队列里 (7,2) (7,3) （ 6，4 ） 统计[2，4]滑动窗口的答案，也是 7
• i==5 a[5]不比队尾元素大，不用弹出队尾，压入新元素 队列里 (7,2) (7,3)（ 6，4 ）（ 5，5 ） 这时候 i 和队首位置差已经超过了滑动窗口长度，弹出队首 队列里 (7,3) （ 6，4 ）（ 5，5 ） 这个窗口答案也为 7

复杂度分析

时间复杂度：每个元素进队出队都只有一次，所以复杂度是 O(N)的 空间复杂度：队列里元素最多为 N 个,所以空间复杂度也是 O(N)

public class Solution {     /**      * @param nums: A list of integers.      * @param k: An integer      * @return: The maximum number inside the window at each moving.      */     public List<Integer> maxSlidingWindow(int[] nums, int k) {         // write your code here         // 答案数组和单调队列         List<Integer> ans = new ArrayList<Integer>();         Deque<Integer> qmax = new LinkedList<Integer>();         int n = nums.length;         for(int i = 0; i < n; i++) {             //维护单调性             while(!qmax.isEmpty() && nums[i] > nums[qmax.getLast()])                 qmax.removeLast();             //滑动窗口的长度超过了 k 删掉超过的部分             if(!qmax.isEmpty() && i - qmax.getFirst() >= k)                 qmax.removeFirst();              qmax.addLast(i);              //统计答案             if(i >= k - 1) {                 ans.add(nums[qmax.getFirst()]);             }         }         return ans;     } }