Leetcode : Sliding Window Maximum
Diffculty：Hard
关键字：滑动窗口，Deque
描述：
给一个数组 nums 和一个窗口大小 k 。
假定你只能看到窗口内的数字，每次窗口移动，滑动一格。
（k总是有效的， 1<= k <= nums.length ）
要求：
返回每次窗口中的数字的最大值，组成的数组。
举栗：
Input：nums=[1,3,-1,-3,5,3,6,7], k=3
OutPut: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[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
【要求】：在线性时间内解决问题
解题方法
一、堆排序。
这是我最先想到的办法。
具体思路：
可以构建k个元素的一个大顶堆。
每次滑动窗口，就相当于前一个元素出堆，后一个元素入堆。
时间复杂度：O(N logk)
比较接近线性时间了，但还是不够。
（代码太简单我就不写了，就是构建大顶堆，出堆和入堆）
二、使用Deque（双端队列）
在石杉的架构笔记看到的。
具体思路：
利用Java已有的双端队列，初始化一个Deque。该队列中保存的是 元素在nums中的索引值(index)。
滑动窗口时，保证：
1）往队列尾部追加节点时，要保证，该节点左边索引在num中的值，要始终大于右边的。如果不大于，则先把尾部节点逐个移除，直到满足条件，再往尾部追加节点。
保证队列的头节点索引所在的num值最大，并且严格按照向右递减
2）队列的头部节点的索引值，不能超出窗口范围。如果超出了，则移除该头节点。
3）由于队列头节点索引在num中的值是最大的，所以每次只要取头结点的值，然后根据该索引取num中的值即可。
话不多说，上代码：
public static int[] maxSlidingWindow(int[] nums, int k){
if(nums==null || nums.length<=0 ){
return new int[0];
}
int[] res = new int[nums.length-k+1];
Deque<Integer> deque = new LinkedList<>();
for(int i=0; i<nums.length; i++){
// 保证队列尾部的元素index 都比左边小.(也就是严格按从大到小value 的 index 顺序)
while(!deque.isEmpty() && nums[i] >nums[deque.getLast()]){
deque.removeLast();
}
// 向队列尾部添加元素(index)
deque.addLast(i);
// 移除超出窗口的头部元素(index)
if(deque.getFirst() <= i-k){
deque.removeFirst();
}
// 保存结果(当i移动到窗口大小时才开始保存结果)
if(i>=k-1){
res[i-k+1] = nums[deque.getFirst()];
}
}
return res;
}
LeetCode 执行结果：
RunTime：10ms (beats 76.37%)
Memory： 42.2MB (beats 65.32%)
参考：
石杉的架构笔记-滑动窗口面试题
