题目
有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。
例如，数组为【4,3,5,4,3,3,6,7】，窗口大小为3时：
窗口数组 最大值
[4 3 5] 4 3 3 6 7 5
4 [3 5 4] 3 3 6 7 5
4 3 [5 4 3] 3 6 7 5
4 3 5 [4 3 3] 6 7 4
4 3 5 4 [3 3 6] 7 6
4 3 5 4 3 [3 6 7] 7
如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。
请功能实现一个函数，
输入：整型数组arr，窗口大小为w；
输出：一个长度为n-w+1的数组res，res【i】表示每一种窗口状态下的最大值。
以本题为例，结果应该返回【5,5,5,4,6,7】
分析
本题的关键是利用双端队列来实现窗口最大值的更新，窗口中的最大值可以覆盖掉该最大值之前的数字信息，利用这一特性来设计双端队列。
设双端队列为qmax，假设遍历到arr[i]：
qmax的放入规则为：
1、若qmax为空，则直接将i放入qmax
2、若qmax不为空，则比较arr[i]与arr[qmax.peekLast()]，
若arr[i]<arr[qmax.peekLast()]，则直接将i放入qmax；
若arr[i]>=arr[qmax.peekLast()]，则将qmax对尾弹出，重新执行第2步。
qmax的弹出规则为：
若qmax队头的下标等于i-w，则说明当前qmax队头的下标已过期，弹出当前队头。
该算法的时间复杂度为O（n）
public class GetMaxWindow {
public int[] getMaxWindow(int[] arr, int w) {
if(arr == null || arr.length == 0) {
return null;
}
int i = 0;
int index = 0;
int[] res = new int[arr.length - w + 1];
LinkedList<Integer> max = new LinkedList<>();
while (i < arr.length) {
while (!max.isEmpty() && arr[i] >= arr[max.peekLast()]) {
max.pollLast();
}
max.offerLast(i);
if (max.peekFirst() == i - w) {
max.pollFirst();
}
//确保窗口已经形成
if (i >= w - 1) {
res[index++] = arr[max.peekFirst()];
}
i++;
}
return res;
}
