给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。
返回滑动窗口最大值。
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7 这题是剑指的一道题，因为滑动窗口的长度是固定的，即当滑动窗口开始移动时，左边的元素出队，右边的元素入队（先进先出），换一个思路就是相当于是求一个队列中的最大值。和leetcode-155的最小栈类似，我们搞了一个辅助栈用来存放历史的最大值，那么这题我们可以采用一个类似的想法，用一个辅助队列来存放历史的最大值。
那么什么样的值可能成为窗口的最大值呢。和剑指一样，我们用一组数据来模拟辅助队列的情况。
滑动窗口的位置 辅助队列 解释
[1],3,-1,-3,6,3,5,7 1 队列空，此时1为窗口最大值
[1,3],-1,-3,6,3,5,7 3 3>1,1不可能成为窗口的最大值了
[1,3,-1],-3,6,3,5,7 3,-1 -1<3,如果3滑出窗口,-1有可能成为窗口最大值
1,[3,-1,-3],6,3,5,7 3,-1,-3 -3<-1,如果3,-1滑出窗口,-3有可能成为窗口最大值
1,3,[-1,-3,6],3,5,7 6 3滑出窗口,辅助队列变成[-1,-3];又6>-1,-1和-3都不可能成为窗口最大值
1,3,-1,[-3,6,3],5,7 6,3 3<6,如果6滑出窗口,3有可能成为窗口最大值
1,3,-1,-3,[6,3,5],7 6,5 5>3,即使6滑出窗口,3也不可能成为窗口最大值
1,3,-1,-3,6,[3,5,7] 7 6滑出窗口,辅助队列变成[5];又7>5,5不可能成为窗口最大值了这样一来思路就很明确了，相当于每次我们都要清除辅助队列中比当前值小的元素：
- 如果当前窗口的右端的值大于辅助队列的队头，清空队列（队头元素应该是辅助队列的最大值）；
- 如果队尾小于当前窗口右端，队尾就出队，直到找到比当前值大的队尾；
另外，因为要考虑到队列中的值滑出窗口的情况，所以辅助队列中存放的是窗口元素的地址，这样当窗口左指针大于辅助队列中存放值的时候，辅助队列中的元素就出列。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length==0 || k==0) return new int[0];
Deque<Integer> deque=new LinkedList<>();
int[] res=new int[nums.length-k+1];
int l=0,r=0;
while (l<=nums.length-k && r<nums.length){
//去除已经滑出窗口的最大值
while (!deque.isEmpty() && deque.peekFirst()<l) deque.pollFirst();
//如果当前值大于队头，清空队列
while (!deque.isEmpty() && nums[deque.peekFirst()]<nums[r]) deque.pollFirst();
//如果当前值大于队尾值，队尾出队
while (!deque.isEmpty() && nums[deque.peekLast()]<nums[r]) deque.pollLast();
//当前值进队
deque.addLast(r);
if (r-l+1==k) {
res[index++]=nums[deque.peekFirst()];
l++;
}
r++;
}
return res;
}
}