输入：一个int数组nums，int k = 窗口大小
输出：每个窗口内的最大值
规则：每次向右移动一个位置。每次窗口内可以看到k个数。将算法优化到O(n)。
例如：输入nums = [1,3,-1,-3,5,3,6,7], and k = 3,输出：[3,3,5,5,6,7]
暴力分析：遍历每个窗口内的数找到最大值。有n-k+1个窗口。算法复杂度O(nk)。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
使用队列：我们知道进一步的优化就是使用最大堆，将数值比较的部分由O(k)变为O(logk)。但仍然不满足要求。可以使用一个双端队列deQue，存放数组下标。
deQue满足两个条件：1 队列内的元素都是窗口内的元素下标；2 队列头部是数值最大的元素下标。
例如：nums = [1,3,-1,-3,5,3,6,7], and k = 3，output是返回值
i=0，队列：0
i=1,队列：1(先从对头删除不是窗口内的元素，其次从队尾开始比较删除比nums[i]小的元素)
i=2,队列：1->2,output[0] = nums[1]=3
i=3,队列：1->3,output[1] = nums[1] =3
i=4,队列：先从对头删除不是窗口内的元素,1被删除；其次从队尾开始比较删除比nums[4]小的元素：队列为空；插入元素4。最终队列：4，output[2] =nums[4]=5.
i=5,队列：4->5,output[3] =nums[4]=5.
i=6,队列：6,output[4] =nums[6]=6.
i=7,队列：7,output[5] =nums[7]=7.
private int[] nums;
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length==0) return new int[]{};
this.nums = nums;
int n = nums.length;
if(n*k == 0) return new int[]{0};
Deque<Integer> deQue = new ArrayDeque<Integer>();
for(int i=0;i<k;i++){
cleanDque(i,k,deQue);
deQue.offerLast(i);
}
int[] maxs = new int[n-k+1];
for(int i=k;i<n;i++){
maxs[i-k] = nums[deQue.peekFirst()];
cleanDque(i,k,deQue);
deQue.offerLast(i);
}
maxs[n-k] = nums[deQue.peekFirst()];
return maxs;
}
private void cleanDque(int i,int k,Deque<Integer> deQue){
if(!deQue.isEmpty() && deQue.getFirst() == i-k){
deQue.pollFirst();
}
while(!deQue.isEmpty() && nums[deQue.peekLast()] < nums[i]){
deQue.pollLast();
}
}
参考链接：url