给定一个长度为100万的数组和一个大小为k的滑动窗口，要求输出窗口每次移动后的最大值。最直观的做法是：对每个窗口位置，遍历窗口内的所有元素找出最大值——总的时间复杂度是$O(n \times k)$。当k接近n时，这退化成了$O(n^2)$。

但如果换一种思路：用一个双端队列维护窗口内元素的"候选冠军"。每当新元素进入窗口，就把队列中所有比它小的元素弹出——这些元素永远不可能成为最大值了。当窗口移动时，只需检查队首元素是否已经离开窗口。这样每个元素最多入队一次、出队一次，时间复杂度直接降到$O(n)$。

这就是单调队列算法的核心魅力：通过维护队列内元素的单调性，将滑动窗口的最值查询优化到线性时间。

单调队列的本质：动态维护窗口内的"潜力股"

单调队列（Monotonic Queue）是一种特殊的队列结构，其内部元素始终保持单调递增或单调递减的顺序。它不是一个独立的基础数据结构，而是对双端队列（Deque）的一种特殊使用方式——通过在入队时主动弹出破坏单调性的元素，来维护队列的有序性。

理解单调队列的关键在于"淘汰"的概念。当元素入队时，那些比它小（或大）的元素可以被淘汰，因为在新元素存在的范围内，这些旧元素永远不会成为答案。队列中存储的是那些"仍有希望"成为最值的元素，而队列的单调性保证了我们能高效地获取当前最优解。

单调队列与单调栈有着相似的"单调性"内核，但存在本质区别：

特性 单调栈 单调队列
操作端 仅栈顶一端 队首和队尾两端
元素生命周期 先进后出，无法移除 先进先出，可从两端移除
核心应用 寻找下一个更大/更小元素 滑动窗口最值问题
是否考虑窗口边界 否 是，需要弹出过期元素

简单来说，单调栈解决"第一次"问题，单调队列解决"当前窗口"问题。单调栈不需要关心元素何时过期，而单调队列必须追踪每个元素的位置，及时清理已经滑出窗口的元素。

两种类型：递增队列与递减队列

单调队列分为两种基本类型，分别对应不同的应用场景：

单调递减队列：队首到队尾元素依次减小。用于解决"滑动窗口最大值"问题。新元素入队时，弹出所有比它小的队尾元素。

单调递增队列：队首到队尾元素依次增大。用于解决"滑动窗口最小值"问题。新元素入队时，弹出所有比它大的队尾元素。

无论是哪种类型，单调队列的核心操作都包含三个步骤：

  1. 入队处理：新元素从队尾入队前，先弹出所有破坏单调性的队尾元素
  2. 过期清理：检查队首元素是否已经滑出窗口，如果是则弹出
  3. 取值：队首元素就是当前窗口的最值

一个重要的实现细节：队列中存储的是元素的下标而非值。存储下标有两个好处：一是可以判断元素是否过期（下标 < 当前窗口左边界），二是可以通过下标快速访问原始数组中的值。

通用模板：单调队列的标准实现

掌握了核心原理后，我们来看单调队列的通用代码模板。以下以单调递减队列（求最大值）为例：

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：移除过期的队首元素（滑出窗口）
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 步骤2：维护单调性，弹出所有比当前元素小的队尾元素
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        // 步骤3：当前元素入队
        deque.offerLast(i);
        
        // 步骤4：如果窗口已形成，记录结果
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    
    return result;
}

这个模板包含四个关键操作：

过期清理：deque.peekFirst() < i - k + 1 判断队首元素是否已经滑出窗口。窗口范围是 $[i-k+1, i]$，任何下标小于 $i-k+1$ 的元素都已过期。

单调维护：nums[deque.peekLast()] < nums[i] 保证队列单调递减。如果队尾元素比当前元素小，它永远不会成为窗口内的最大值，直接弹出。

元素入队：将当前元素的下标加入队尾。注意，此时队列中所有比它小的元素都已被弹出，队列仍然保持单调递减。

结果获取：当 $i \geq k-1$ 时，窗口已经形成，队首元素就是当前窗口的最大值。

复杂度分析

时间复杂度：$O(n)$。每个元素最多入队一次、出队一次，所有操作的总次数与n成正比。

空间复杂度：$O(k)$。队列中最多同时存在k个元素（一个完整窗口的大小）。

LeetCode 239：滑动窗口最大值

这是单调队列最经典的应用场景，也是理解该数据结构的最佳切入点。

题目描述：给定一个整数数组 nums 和一个整数 k，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧，返回每次滑动窗口中的最大值。

示例：

输入：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

完整Java实现：

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0 || k == 0) return new int[0];
        if (k == 1) return nums;
        
        int[] result = new int[n - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i < n; i++) {
            // 移除过期的队首元素
            if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            
            // 维护单调递减性
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
            
            // 记录结果
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return result;
    }
}

执行过程演示（以 nums = [1,3,-1,-3,5,3,6,7], k = 3 为例）：

i nums[i] 操作 队列状态（下标） 队列值 结果
0 1 1入队 [0] [1] -
1 3 弹出0，1入队 [1] [3] -
2 -1 -1入队 [1,2] [3,-1] 3
3 -3 -3入队 [1,2,3] [3,-1,-3] 3
4 5 弹出1,2,3，5入队 [4] [5] 5
5 3 3入队 [4,5] [5,3] 5
6 6 弹出4,5，6入队 [6] [6] 6
7 7 弹出6，7入队 [7] [7] 7

关键观察：当遇到一个较大的元素时，队列中所有比它小的元素都会被"淘汰"，因为在新元素存在的窗口范围内，这些小元素永远不会成为最大值。

LeetCode 862：和至少为K的最短子数组

这道题展示了单调队列处理前缀和问题的威力，是单调队列的进阶应用。

题目描述：给定一个整数数组 nums 和一个整数 k，返回 nums 中和至少为 k 的最短非空子数组的长度。如果不存在这样的子数组，返回 -1。

关键洞察：子数组和可以通过前缀和快速计算。设前缀和数组为 prefixSum，则子数组 nums[i..j] 的和为 prefixSum[j+1] - prefixSum[i]。问题转化为：找到最小的 j - i + 1，使得 prefixSum[j+1] - prefixSum[i] >= k。

为什么需要单调队列：对于每个位置 j，我们需要找到最小的 i 使得 prefixSum[i] <= prefixSum[j+1] - k。如果前缀和数组不是单调的，暴力搜索会超时。单调队列可以帮助我们高效地找到满足条件的最小 i。

单调递增队列的应用：维护一个前缀和单调递增的队列。对于当前前缀和 prefixSum[j]，队列中所有满足 prefixSum[j] - prefixSum[队首] >= k 的队首元素都可以作为候选的 i，我们取最小的那个。

class Solution {
    public int shortestSubarray(int[] nums, int k) {
        int n = nums.length;
        long[] prefixSum = new long[n + 1];
        for (int i = 0; i < n; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
        
        int minLength = Integer.MAX_VALUE;
        Deque<Integer> deque = new ArrayDeque<>();
        
        for (int i = 0; i <= n; i++) {
            // 尝试用当前前缀和减去队首前缀和
            while (!deque.isEmpty() && prefixSum[i] - prefixSum[deque.peekFirst()] >= k) {
                minLength = Math.min(minLength, i - deque.pollFirst());
            }
            
            // 维护前缀和的单调递增性
            while (!deque.isEmpty() && prefixSum[deque.peekLast()] >= prefixSum[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
        }
        
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}

为什么使用单调递增队列：我们要找的是 prefixSum[i] <= prefixSum[j] - k 的最小 i。如果队列中的前缀和是递增的，那么队首就是最小的前缀和，最容易满足条件。

LeetCode 1438：绝对差不超过限制的最长连续子数组

这道题需要同时维护窗口内的最大值和最小值，展示了单调队列的另一面。

题目描述：给定一个整数数组 nums 和一个整数 limit，返回最长连续子数组的长度，该子数组中任意两个元素之间的绝对差必须小于或等于 limit。

解题思路：窗口的最大值和最小值之差如果超过 limit，就需要收缩窗口。使用两个单调队列分别维护窗口内的最大值和最小值。

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxDeque = new ArrayDeque<>();  // 单调递减，队首是最大值
        Deque<Integer> minDeque = new ArrayDeque<>();  // 单调递增，队首是最小值
        
        int left = 0, maxLength = 0;
        
        for (int right = 0; right < nums.length; right++) {
            // 维护最大值队列（单调递减）
            while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] < nums[right]) {
                maxDeque.pollLast();
            }
            maxDeque.offerLast(right);
            
            // 维护最小值队列（单调递增）
            while (!minDeque.isEmpty() && nums[minDeque.peekLast()] > nums[right]) {
                minDeque.pollLast();
            }
            minDeque.offerLast(right);
            
            // 收缩窗口直到满足条件
            while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
                left++;
                if (maxDeque.peekFirst() < left) maxDeque.pollFirst();
                if (minDeque.peekFirst() < left) minDeque.pollFirst();
            }
            
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

LeetCode 1696：跳跃游戏VI（单调队列优化DP）

这道题展示了单调队列在动态规划优化中的应用。

题目描述：给定一个下标从 0 开始的整数数组 nums 和一个整数 k。一开始在下标 0 处，每一步最多可以往前跳 k 步。目标是到达数组最后一个位置（下标 nums.length - 1），得分为经过的所有数字之和，返回能获得的最大得分。

动态规划思路：设 dp[i] 表示到达位置 i 能获得的最大得分。状态转移方程为：

$$dp[i] = nums[i] + \max_{j \in [i-k, i-1]} dp[j]$$

暴力求解需要 $O(n \times k)$ 时间。但注意到当 $i$ 增加时，转移来源的范围也是向右滑动的——这正是滑动窗口最大值问题！

单调队列优化：用单调递减队列维护窗口内的最大 dp 值，将时间复杂度优化到 $O(n)$。

class Solution {
    public int maxResult(int[] nums, int k) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offerLast(0);
        
        for (int i = 1; i < n; i++) {
            // 移除过期的队首元素
            while (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }
            
            // 当前dp值 = nums[i] + 窗口内最大的dp值
            dp[i] = nums[i] + dp[deque.peekFirst()];
            
            // 维护单调递减性
            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
                deque.pollLast();
            }
            
            deque.offerLast(i);
        }
        
        return dp[n - 1];
    }
}

单调队列的应用场景识别

判断一道题是否适合使用单调队列，可以从以下几个特征入手：

滑动窗口最值问题：题目明确要求在一个移动窗口内找到最大值或最小值。

动态规划中的窗口转移：DP状态转移依赖于前面固定范围内的最值，且范围随当前位置右移。

前缀和配合单调性：涉及子数组和的问题，且需要利用前缀和的单调性进行优化。

需要同时追踪位置和值：问题要求在元素过期时能够快速移除，这时存储下标的单调队列尤为有效。

总结

单调队列是将双端队列的"两端操作"特性与"单调性维护"思想相结合的产物。它的核心价值在于：

时间复杂度优化：将滑动窗口最值问题从 $O(n \times k)$ 优化到 $O(n)$，实现了本质性的效率提升。

通用性强：不仅适用于基础的滑动窗口问题，还能优化动态规划、处理前缀和问题，是一个多功能工具。

实现简洁：核心代码不超过20行，但需要正确理解三个关键操作：过期清理、单调维护、结果获取。

掌握单调队列的关键在于理解"淘汰无用元素"的贪心思想——那些永远不会成为答案的元素，应该在入队时就被清理掉。这种思想不仅适用于单调队列，也是许多高效算法的共同特征。