题目
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- -----
[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
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
- $1 <= nums.length <= 10^5#
- $10^4 <= nums[i] <= 10^4$
1 <= k <= nums.length
分析
可以采用双指针遍历，更新滑动窗口的最大值：
- 最大值下标，大于left
- 最右值大于等于窗口最大值，则更新最大值及其下标
- 最右值大于等于窗口最大值 - 1，则更新最大值及其下标
- 最左值大于等于窗口最大值 - 1，则更新最大值及其下标
- 最坏的情况：从left遍历到right，记录最大值及其下标
双指针遍历
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int left = 0, right = k - 1;
int maxindex = -1;
int max = Integer.MIN_VALUE;
int[] ans = new int[nums.length - k + 1];
while (right < nums.length) {// 没超过最大值
// 巧妙利用if else的分支只选一个执行的特性
if (left <= maxindex) { // 这种情况，直接根据最右值更新
if (nums[right] >= max) {
max = nums[right];
maxindex = right;// 更新最大值下标
}
} else if (nums[right] >= max - 1) {// 右侧最大值更新
max = nums[right];
maxindex = right;
} else if (nums[left] >= max - 1) {// 左侧最大值更新
max = nums[left];
maxindex = left;
} else {
// 最坏的情况，需要扫描一边更新一个最大值
max = nums[left];
for (int i = left + 1; i <= right; i++) {
if (nums[i] >= max) {
max = nums[i];
maxindex = i;
}
}
}
ans[left] = max;
left++;
right++;
}
return ans;
}
}
优先队列维护最大值
优先队列存储k个元素，维护最大值。更新窗口，然后自动更新最大值。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// 优先队列，内部元素是长度为2的数组，第一个是值 第二个是下标
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
// 放入k个元素
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];// 更新最大值数组
}
return ans;
}
}
单调队列
采用一个单调递减队列，维护最大值下标
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
// 移出较小值的下标
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);// 加入当前值，这个值是窗口的最小值
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];// peekFirst 是最大值下标
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
// 最大值下标只最左侧的下标，需要移除
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
分块 + 预处理
稀疏表思想
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] prefixMax = new int[n];// 后缀最大值数组
int[] suffixMax = new int[n];// 前缀最大值数组
for (int i = 0; i < n; ++i) {
if (i % k == 0) {// 块的边缘，直接赋值
prefixMax[i] = nums[i];
} else {
prefixMax[i] = Math.max(prefixMax[i - 1], nums[i]);
}
}
for (int i = n - 1; i >= 0; --i) {
if (i == n - 1 || (i + 1) % k == 0) {// 块的边缘，直接赋值
suffixMax[i] = nums[i];
} else {
suffixMax[i] = Math.max(suffixMax[i + 1], nums[i]);
}
}
// 遍历最大最小前缀数组
int[] ans = new int[n - k + 1];
for (int i = 0; i <= n - k; ++i) {
ans[i] = Math.max(suffixMax[i], prefixMax[i + k - 1]);
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
