题目：有一个整型数组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
输入：整型数组arr（长度为n），窗口大小 w
输出：一个长度为 n-w+1 的数组res，res[i]表示每一种窗口状态下的最大值。以上面为例，返回的为 res[5，5，5，4，6，7]
方法一：(存在个别用例超时)
思路：
1）定义两个指针 left ，right ，每次两个指针一起向下走一个位置。
2）进入while循环，知道right指针走到最后停止
3）在while循环中，遍历窗口中元素，把最大值复制给变量 max，然后将每次找到的最大值加入res数组中。
/*
* 生成窗口最大值数组
* */
public static int[] getMaxWindow(int[] arr, int w) {
//双指针 右指针最大值为数组长度-1
int left = 0;
int right = left + w -1;
int[] res = new int[arr.length-w+1];
int max = Integer.MIN_VALUE;
int index = 0;
while (right <= arr.length-1){
for (int i = left;i <= right;i++) {
//找到这个窗口的最大值并返回
if (arr[i] > max) {
max = arr[i];
}
res[index] = max;
}
max = Integer.MIN_VALUE;
left++;
right++;
index++;
}
return res;
}
存在超时问题：
方法二：
使用双端队列
生成双端队列 qmax，qmax 中存放数组 arr 中的下标。假设遍历到arr[i]，
qmax放入规则：
（1）如果 qmax 为空，直接把下标 i 放进 qmax，放入过程结束。
（2）如果 qmax 不为空，取出当前 qmax 队尾存放的下标，假设为 j 。
1）如果 arr[j] > arr[i] 直接把下标 i 放进qmax的队尾，放入过程结束
2）如果 arr[j] <= arr[i] 把 j 从qmax中弹出，重复qmax放入规则。
也就是说，如果 qmax 是空的，就直接放入当前的位置。
如果 qmax 不是空的，qmax 队尾的位置所代表的值 <= 当前的值，就弹出队尾的位置。
如果qmax 队尾的位置所代表的值 > 当前的值，当前的位置就放入 qmax 的队尾。
qmax弹出规则：
如果 qmax 队头的下标等于 i-w ，说明当前 qmax 队头的下标已过期，弹出当前队头的下标即可。
本题过程： 4 3 5 4 3 3 6 7
（1）qmax为空
（2）arr[0] = 4，下标0放入qmax，qmax={0}
（3）arr[1] = 3 arr[0] > arr[1] ，下标1放入，qmax={0,1}
（4）arr[2] = 5 arr[1] < arr[5]，队尾位置弹出，下标2进去，qmax={2}，此时出现第一个窗口 【0..2】，最大值为arr[2] = 5。
（5）arr[3] = 4 arr[2] > arr[3]，下标3进去，qmax={2,3}，第二个窗口【1..3】出现，最大值为arr[2] = 5
（6）arr[4] = 3 arr[3] > arr[4]，下标4进去，qmax={2,3,4}，第三个窗口【2..4】出现，最大值还是5
（7）arr[5] = 3 arr[4] = arr[5]，下标4弹出，下标5放入，qmax={2,3,5}，第四个窗口【3..5】出现，下标2已经过期，弹出，qmax={3,5}，最大值为 arr[3] = 4
（8）arr[6] = 6 arr[5] < arr[6]，下标5弹出，arr[3] <arr[6]，下标3也弹出，6进去，qmax={6}，
第五个窗口出现，最大值为arr[6]=6
（9）arr[7] = 7 arr[6] < arr[7]，下标6弹出，7进去，qmax={7}，第六个窗口出现，最大值为7
代码实现：
public static int[] getMaxWindow2(int[] arr, int w) {
if (arr == null || w < 1 || arr.length < w) {
return null;
}
//定义双端队列
LinkedList<Integer> qmax = new LinkedList<>();
int[] res = new int[arr.length - w + 1];
int index = 0;
//遍历数组
for (int i = 0; i < arr.length; i++) {
//如果qmax不为空 且 双端队列末尾元素代表的值 <= 当前遍历到的值，就把末尾元素弹出
while (!qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]){
qmax.pollLast();
}
qmax.addLast(i);
//判断下标是否过期
if (qmax.peekFirst() == i-w) {
qmax.pollFirst();
}
if (i >= w -1) {
res[index++] = arr[qmax.peekFirst()];
}
}
return res;
}版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/87979.html
