题目: 给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 实例:
package question;
import java.util.LinkedList;
/**
* @author keke
* @version 1.0
* @className Question112
* @description
* @time 2022/8/20 22:20
*/
public class Question112 {
public static void main(String[] args) {
int[] nums = new int[]{1, 3, -1, -3, 5, 3, 6, 7};
int k = 3;
int[] maxs = maxSlidingWindow(nums, k);
for (int max : maxs) {
System.out.println(max);
}
}
private static int[] maxSlidingWindow(int[] nums, int k) {
// 用来保存每个窗口的最大值
int[] result = new int[nums.length - k + 1];
LinkedList<Integer> queue = new LinkedList<>();
// 下标从0开始,遍历数组,rightIndex 表示滑动窗口右边界
for (int rightIndex = 0; rightIndex < nums.length; rightIndex++) {
// 用 while 循环,当队列非空时,数组滑动新的元素大于等于队尾的元素,则队尾的元素移掉,因为不是最大值
// while 循环结果添加,队列空了,或者数组滑动新的元素小于队尾的元素
while (!queue.isEmpty() && nums[rightIndex] >= nums[queue.peekLast()]){
queue.removeLast();
}
// 存储数组右滑的下标
queue.addLast(rightIndex);
// 计算窗口左侧边界
int leftIndex = rightIndex - k + 1;
// 队首的元素是整个窗口里最大的,但是当数组滑动是,队首的元素已经不在窗口内,就要移除掉
if (queue.peekFirst() < leftIndex){
queue.removeFirst();
}
// 因为数组的下标是从0开始,只有窗口右边界的下标+1>=k的值时,才能比较取窗口的最大值(队首的元素)
if (rightIndex + 1 >= k){
result[leftIndex] = nums[queue.peekFirst()];
}
}
return result;
}
}