双指针与滑动窗口困难2 种解法
#239滑动窗口最大值
返回长度为 k 的窗口从左向右滑动时，每个窗口中的最大值。
#数组#滑动窗口#单调队列#优先队列
原题
给你一个整数数组 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 <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
解题主线
- 单调队列保存下标而不是值，才能同时判断元素大小与是否已经离开窗口。
- 队列中的值单调递减；新值会淘汰队尾所有不大于它的旧值，因为这些旧值更小且更早过期。
- 最大堆可用下标惰性删除过期元素：只有堆顶离开窗口时才需要弹出。
解法 1：单调递减队列
队列维护当前窗口内仍可能成为最大值的下标；先删过期队头，再删不优于新元素的队尾，队头即窗口答案。
-
时间复杂度： O(n)，每个下标最多入队、出队各一次
-
空间复杂度： O(k)
import java.util.ArrayDeque;
import java.util.Deque;
final class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
validate(nums, k);
if (nums.length == 0) return new int[0];
int[] maximums = new int[nums.length - k + 1];
Deque<Integer> decreasing = new ArrayDeque<>();
for (int right = 0; right < nums.length; right++) {
// 队头下标已离开当前窗口时立即移除
while (!decreasing.isEmpty() && decreasing.peekFirst() <= right - k) {
decreasing.pollFirst();
}
// 淘汰更小且更早过期的队尾，保持对应值单调递减
while (!decreasing.isEmpty()
&& nums[decreasing.peekLast()] <= nums[right]) {
decreasing.pollLast();
}
decreasing.offerLast(right);
// 形成完整窗口后，队头始终是当前最大值下标
if (right >= k - 1) {
maximums[right - k + 1] = nums[decreasing.peekFirst()];
}
}
return maximums;
}
private void validate(int[] nums, int k) {
if (nums == null) throw new IllegalArgumentException("nums must not be null");
if (nums.length == 0) {
if (k != 0) throw new IllegalArgumentException("k must be 0 for an empty array");
return;
}
if (k <= 0 || k > nums.length) {
throw new IllegalArgumentException("k must be in [1, nums.length]");
}
}
}解法 2：最大堆与惰性删除
堆中保存值和下标并让最大值、较新下标优先；加入新元素后，持续弹出已离开当前窗口的堆顶。
-
时间复杂度： O(n log n) 最坏；每个元素入堆一次、出堆至多一次
-
空间复杂度： O(n) 最坏，惰性删除会保留暂未到堆顶的过期项
import java.util.PriorityQueue;
final class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
validate(nums, k);
if (nums.length == 0) return new int[0];
PriorityQueue<int[]> maximums = new PriorityQueue<>((first, second) -> {
int byValue = Integer.compare(second[0], first[0]);
return byValue != 0
? byValue
: Integer.compare(second[1], first[1]);
});
int[] answer = new int[nums.length - k + 1];
for (int right = 0; right < nums.length; right++) {
maximums.offer(new int[] {nums[right], right});
// 只需惰性删除堆顶中过期的下标，非堆顶旧项不影响答案
while (maximums.peek()[1] <= right - k) {
maximums.poll();
}
// 完整窗口形成后，堆顶即当前窗口最大值
if (right >= k - 1) {
answer[right - k + 1] = maximums.peek()[0];
}
}
return answer;
}
private void validate(int[] nums, int k) {
if (nums == null) throw new IllegalArgumentException("nums must not be null");
if (nums.length == 0) {
if (k != 0) throw new IllegalArgumentException("k must be 0 for an empty array");
return;
}
if (k <= 0 || k > nums.length) {
throw new IllegalArgumentException("k must be in [1, nums.length]");
}
}
}实现提示
- 较新下标在值相同时优先，可以更早淘汰已经离开窗口的旧副本；Integer.compare 避免减法溢出。
边界与易错点
- 旧堆比较器使用 o2[0] - o1[0] 和 o2[1] - o1[1]，极端整数可能溢出并破坏比较器契约；整理后统一使用 Integer.compare。
- 单调队列队头过期条件是 index <= right - k；边界写错一位会保留上一个窗口的元素。
- 堆的惰性删除会让非堆顶过期项暂时残留，因此最坏空间是 O(n)，不能误写成 O(k)。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
leetcode/src/main/java/zhard/Q239_maxSlidingWindow.java