滑动窗口最大值：单调队列 O(n) 解法的精妙之处

老张2026/4/30大约 7 分钟

滑动窗口最大值：单调队列 O(n) 解法的精妙之处

适读人群：Java 后端工程师、算法高阶学习者 | 阅读时长：约 20 分钟 | 难度：⭐⭐⭐⭐

开篇故事

LeetCode 239 是我做过的最有"设计感"的题目之一。每次在课堂上讲这道题，学员们第一次看到单调队列的解法时，都会有那种"哦！就是这样！"的顿悟感。

这道题的难点不在代码量，而在于需要想到一个非直觉的数据结构——单调队列（Monotonic Deque）。

普通队列是先入先出，而单调队列在入队时会维护队列的单调性：如果新入队的元素比队尾的元素大（对于维护最大值），就把队尾弹出，直到队列为空或队尾比新元素大为止。这样，队头始终是当前窗口的最大值。

听起来有点绕，但看了代码示例之后，你会发现这个设计极为简洁而优雅。

一、题目解析

题目（LeetCode 239）： 给一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧，每次移动一位。返回每个窗口中的最大值组成的数组。

示例：

nums = [1,3,-1,-3,5,3,6,7]，k = 3
输出：[3,3,5,5,6,7]

关键要求： O(n) 时间，每个窗口位置 O(1) 时间。

二、解法一：暴力 O(nk)

public class Solution1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int max = nums[i];
            for (int j = i + 1; j < i + k; j++) {
                max = Math.max(max, nums[j]);
            }
            result[i] = max;
        }
        return result;
    }
}

复杂度分析

时间复杂度：O(nk)。
空间复杂度：O(1)（不计结果数组）。

三、解法二：有序集合（TreeMap）O(n log k)

public class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // TreeMap<值, 出现次数> 维护窗口内的元素
        TreeMap<Integer, Integer> map = new TreeMap<>();

        // 初始化第一个窗口
        for (int i = 0; i < k; i++) {
            map.merge(nums[i], 1, Integer::sum);
        }
        result[0] = map.lastKey();

        for (int i = k; i < n; i++) {
            // 加入新元素
            map.merge(nums[i], 1, Integer::sum);
            // 移出旧元素
            int outgoing = nums[i - k];
            if (map.get(outgoing) == 1) map.remove(outgoing);
            else map.merge(outgoing, -1, Integer::sum);
            result[i - k + 1] = map.lastKey();
        }
        return result;
    }
}

复杂度分析

时间复杂度：O(n log k)。每次 TreeMap 操作 O(log k)。
空间复杂度：O(k)。TreeMap 存 k 个元素。

四、解法三最优：单调队列 O(n)

单调队列原理

维护一个存下标的双端队列（Deque），队列中的下标对应的值从队头到队尾单调递减。

入队规则（维护单调性）： 新元素 nums[i] 入队前，如果队尾元素对应的值 <= nums[i]，弹出队尾（因为它们在 i 之前，且比 nums[i] 小，窗口滑过时 nums[i] 会比它们更晚失效但更大，所以它们永远不可能成为最大值，可以直接丢弃）。

出队规则（维护窗口范围）： 如果队头元素的下标 <= i - k（已经不在当前窗口内），弹出队头。

取最大值： 队头元素就是当前窗口的最大值（队列单调递减，队头最大；且队头未失效）。

为什么弹出队尾是安全的？

设队尾元素下标为 j，nums[j] <= nums[i]，且 j < i。

当窗口包含 i 时，j 一定也在窗口内（j < i，且 i 进窗口时 j 可能还在）。
若 j 和 i 同时在窗口内，nums[i] >= nums[j]，所以 j 不会是最大值。
若 j 离开窗口时，i 还在窗口内，所以窗口最大值还是由 i（或后续更大的元素）决定，j 依然不会是最大值。

因此，一旦出现比 j 处值更大的后来者 i，j 就永远不可能再作最大值了。弹出是安全的。

Mermaid 图：单调队列滑动窗口

完整代码

public class Solution3 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int[] result = new int[n - k + 1];
        // 单调递减队列（存下标）
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 1. 维护单调性：弹出队尾中所有比 nums[i] 小的元素
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            // 2. 将当前下标加入队尾
            deque.addLast(i);

            // 3. 维护窗口范围：弹出超出窗口的队头
            if (deque.peekFirst() <= i - k) {
                deque.pollFirst();
            }

            // 4. 窗口满时，记录最大值（队头）
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(Arrays.toString(
                sol.maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7}, 3)));
        // [3, 3, 5, 5, 6, 7]

        System.out.println(Arrays.toString(
                sol.maxSlidingWindow(new int[]{1}, 1)));
        // [1]

        System.out.println(Arrays.toString(
                sol.maxSlidingWindow(new int[]{9,11}, 2)));
        // [11]

        System.out.println(Arrays.toString(
                sol.maxSlidingWindow(new int[]{4,-2}, 2)));
        // [4]
    }
}

复杂度分析

时间复杂度：O(n)。每个下标最多入队一次、出队一次，总操作数 O(2n)。
空间复杂度：O(k)。队列最多存 k 个下标。

五、举一反三

题号	题目	单调队列的应用
862	和至少为 K 的最短子数组	单调队列维护前缀和的最小值
918	环形子数组的最大和	单调队列 + 前缀和
1425	带限制的子序列和	dp + 单调队列优化
84	柱状图中最大的矩形	单调栈（与单调队列思路类似）

单调队列的通用模板：

Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
    // 维护单调性（以单调递减为例）
    while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
        deque.pollLast();
    }
    deque.addLast(i);
    // 维护窗口范围（如有需要）
    while (deque.peekFirst() < windowLeft) {
        deque.pollFirst();
    }
    // 使用队头（最大值）
    int max = nums[deque.peekFirst()];
}