双指针与滑动窗口困难2 种解法

#239滑动窗口最大值

返回长度为 k 的窗口从左向右滑动时，每个窗口中的最大值。

#数组#滑动窗口#单调队列#优先队列

解题主线

单调队列保存下标而不是值，才能同时判断元素大小与是否已经离开窗口。

队列中的值单调递减；新值会淘汰队尾所有不大于它的旧值，因为这些旧值更小且更早过期。

最大堆可用下标惰性删除过期元素：只有堆顶离开窗口时才需要弹出。

解法 1：单调递减队列

队列维护当前窗口内仍可能成为最大值的下标；先删过期队头，再删不优于新元素的队尾，队头即窗口答案。

时间复杂度

O(n)，每个下标最多入队、出队各一次

空间复杂度

O(k)

239. 滑动窗口最大值 · 单调递减队列

java

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) 最坏，惰性删除会保留暂未到堆顶的过期项

239. 滑动窗口最大值 · 最大堆与惰性删除

java

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