题目链接：https://leetcode-cn.com/problems/sliding-window-maximum/
分类：
滑动窗口（两种设置左右边界初始值的方法、求滑动窗口内最大值：暴力解法 → 单调队列法）单调队列（基于双向队列，队尾到队首非递减存放窗口内可能成为max的元素，队首 == 当前窗口max）滑动窗口大小 = k，遍历一个窗口 [i, j] 内的所有元素求出max，时间复杂度为O(K)；
窗口滑动一位，[i+1 , j+1]，则新元素nums[j + 1]从右端点加入窗口，原来的左端点nums[i]则需要移出窗口，如果nums[i]是窗口滑动之前的max，现在移除它，滑动窗口里的max就丢失了，需要重新计算，这样又需要O(k)的时间。
以此类推，滑动窗口的左边界 i 从 0 到 n-k，一共移动了n - k + 1次，所以也计算了n-k+1次的max，每次计算max耗时O(k),所以暴力解的时间复杂度为O((n-k+1)k)=O(nk)。
根据暴力解可以发现本题的难点：
如果当前窗口的左端点就是滑动窗口内的max，现在窗口滑动一位需要移除左端点，则滑动后窗口里的max就需要重新计算。每次耗时O(K）。
由此得出优化目标：把求解max的O(k)缩小到O(1)。
要把计算max的时间复杂度缩小为O(1)，自然是要把每个滑动窗口对应的max保存起来，但只保存当前窗口的max远远不够，我们还将窗口内可能成为max的元素也保存起来，且要随着窗口的滑动更新。
1、使用什么数据结构来保存可能成为max的元素？ 使用双向队列，队列里保存的是窗口内可能成为max的元素，且这些元素从队尾到队首按升序排列，队首存放的是整个队列的最大值，也就是滑动窗口的最大值。
每滑动一次窗口，队列就要做一定的调整，具体调整内容见2.
补充：双向队列的使用
Deque<Integer> deque = new LinkedList<>(); deque.removeFirst(); deque.removeLast(); deque.peekLast() ; deque.peekFirst() deque.addLast();2、如何设计出入队规则？ 队列存放的是当前窗口内可能成为max的元素，队首存放当前滑动窗口的max。
设滑动窗口为[i,j]，每次窗口滑动就是左边界+1，右边界+1，即[i+1,j+1]，左端点nums[i]会移出窗口，右端点加入新的元素nums[j+1]。
如果移出窗口的不是滑动窗口的最大值（nums[i] != deque.peekFirst()），则窗口的滑动不会改变当前窗口的最大值，但有可能改变“可能成为max的元素”，所以需要从双向队列的队尾开始往前遍历：
将所有 < nums[j+1] 的元素都出队，因为 nums[j+1]作为窗口的右边界，会是当前窗口最晚移除的元素，所以队列记录的备选元素里只要 < nums[j+1]，就不可能再成为max,将它们移出队列，直到队内元素 >= nums[j+1]或队列为空，再将nums[j+1]从队尾加入。
如果移出窗口的是滑动窗口的最大值，就将队首元素也弹出，顶替上来的就是滑动窗口内的第二大元素，但新加入窗口的元素nums[j+1]也有可能成为窗口最大值，所以在队首弹出之前，要先处理nums[j+1]，处理流程和上面相同。
这样的出入队规则可以确保队列的元素从队尾到队首按非递减排列。
所以滑动一次窗口带来的队列调整可以整理为：
判断移出窗口的左端点nums[i] 是不是窗口的最大值： 如果是最大值，则将队列队首弹出；如果不是最大值，则队列保持不变； 接着处理新加入窗口的nums[j+1]： 从队尾开始，将所有 < nums[j+1]的元素全部弹出，直到队内元素 >= nums[j+1]或队列为空，再将nums[j+1]从队尾加入队中。如果nums[j+1]小于队尾，则队列保持不变。 获取当前队列的队首元素，就是当前窗口的最大值，记录到res数组中，然后开始下一轮滑动。3、滑动窗口的左右边界初始值如何设置？左右边界什么时候开始同步移动？
方法1：[i,j]，初始时i=0,j=0，在j-i<k-1时，每次只有j+1；当j-i=k-1时，左右边界开始同步移动。方法2（采用）：设置初始值i=1-k,j=0,这样一开始i,j就能同步移动。 但是要注意，只有当i > 0 时，窗口滑动才会导致左边界元素被移出窗口，这个时候才要开始对左边界出窗做处理。4、输出数组的设置 因为各个滑动窗口的最大值数量=nums.length - k + 1，所以存放最终max集合的数组res的大小为nums.length - k + 1，
但是要注意：基于3、对初始值的设置，只有当 i >= 0 时窗口滑动得到的max才加入到res中。因为i < 0时窗口左边界在数组有效范围之外，不算真正的窗口。
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { //特殊用例 if(k == 0) return new int[0]; if(k == 1) return nums; Deque<Integer> deque = new LinkedList<>();//双向队列，队首存放当前窗口的max int i = 1 - k, j = 0;//窗口左右边界 int len = nums.length; int[] res = new int[len - k + 1];//存放最终max解集 while(j < len){//每循环一次就是滑动一次窗口，滑动后的窗口是[i,j]，移出的左端点是nums[i-1]，加入的右端点是nums[j] //i>0时开始考虑左端点移出窗口的处理： if(i > 0){ //只有当移出窗口的左端点nums[i-1]等于当前窗口最大值时，才将队首弹出 if(nums[i - 1] == deque.peekFirst()) deque.pollFirst(); //其他情况队列保持不变 } //右端点nums[j]加入窗口的处理： while(!deque.isEmpty() && nums[j] > deque.peekLast()){ //从队尾开始弹出所有 < 右端点的队内元素，直到队尾元素 >=右端点或队列为空 deque.pollLast(); } //直到队尾元素 >= nums[j]或队列为空时，再将nums[j]从队尾加入队中 if(deque.isEmpty() || nums[j] <= deque.peekLast()) deque.addLast(nums[j]); //最后获取当前窗口的最大值：当i>=0时，窗口每滑动一次就向res加入当前窗口的最大值 if(i >= 0) res[i] = deque.peekFirst(); //窗口滑动，左右边界同步移动1位，进入下一轮循环 i++; j++; } return res; } }