07 单调队列优化滑动窗口：O(n) 求窗口极值的艺术

单调队列优化滑动窗口：$O(n)$ 求窗口极值的艺术

摘要

第 01 篇提到，求窗口内最大（最小）值是固定窗口的核心难点——朴素维护会退化到 $O(nk)$。本文系统讲解解决这个问题的核武器：单调双端队列（Monotone Deque）。从单调队列的设计动机出发，推导其不变量维护逻辑，再通过 LeetCode 239（滑动窗口最大值，经典题）、LeetCode 1438（绝对差不超过限制的最长连续子数组，同时维护最大和最小值）、LeetCode 2762（不间断子数组，可变窗口+单调队列）三道题，演示单调队列在固定窗口和可变窗口中的双重用途。

---

第 1 章 为什么需要单调队列

1.1 朴素极值维护的困境

第 01 篇已分析：进窗时更新最大值很简单（max = Math.max(max, nums[right])），但出窗时若出的恰好是最大值，需要扫描整个窗口找新的最大值，$O(k)$ 一次，总体 $O(nk)$。

用有序数据结构（如 TreeMap）可以做到 $O(\log k)$ 一次，总体 $O(n\log k)$。但这还不够好——有没有 $O(1)$ 均摊的方案？

1.2 关键观察：过时的大值永远无用

设当前窗口是 $[l,r]$，其中有两个元素 $nums[i]$ 和 $nums[j]$，$i<j$，且 $nums[i]\le nums[j]$。

此后，当 $j$ 还在窗口内时（还没被 left 越过），$i$ 若在窗口内，$nums[i]$ 永远不可能是窗口最大值（因为 $nums[j]\ge nums[i]$，且 $j$ 比 $i$ 更靠右，会在 $i$ 离窗后仍留在窗口内）。

换句话说：对于窗口内的任意两个元素 $i<j$，如果 $nums[i]\le nums[j]$，那么 $nums[i]$ 对于当前及以后的任意窗口，都不可能成为最大值，可以丢弃。

这就是单调队列的核心思想：维护一个”潜力选手”的有序列表，及时淘汰没有竞争力的候选。

1.3 单调队列的不变量

单调递减的队列（用于维护最大值）：队列中存储的是数组下标（不是元素值），满足以下不变量：

1. 队列中的下标对应的元素值单调递减（从队首到队尾）：nums[deque[0]] >= nums[deque[1]] >= ... >= nums[deque[tail]]
2. 队列中的下标单调递增（从队首到队尾）：deque[0] < deque[1] < ... < deque[tail]（保证队首的元素是最旧的）
3. 队列中所有下标都在当前窗口 $[l,r]$ 内

由不变量可知：队首元素（deque.peekFirst()）对应的下标，就是当前窗口内最大值的下标。

维护这个不变量的操作：

右指针进窗（新元素 nums[right] 入队）：

• 从队尾开始，把所有”值 ≤ nums[right]”的下标从队尾弹出（它们已经没有竞争力了）
• 将 right 加入队尾

左指针出窗（nums[left] 出窗）：

• 如果队首的下标等于 left，说明队首元素已离窗，从队首弹出
• 否则不做任何操作（队首的最大值还在窗口内）

维护操作总结：
进窗：while (队尾值 <= nums[right]) 弹出队尾; 加入 right
出窗：if (队首下标 == left) 弹出队首
查最大：deque.peekFirst() 对应的 nums 值

---

第 2 章 LeetCode 239：滑动窗口最大值

2.1 题目

LeetCode 239 - Sliding Window Maximum（困难）

给你一个整数数组 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

2.2 各解法时间复杂度对比

方法	时间复杂度	空间复杂度	说明
暴力枚举	$O(nk)$	$O(1)$	每次扫描整个窗口
有序集合（TreeMap）	$O(n\log k)$	$O(k)$	维护有序窗口
单调队列	$O(n)$	$O(k)$	均摊 $O(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 right = 0; right < n; right++) {
        // 步骤 1：清理队尾。把所有 <= nums[right] 的下标从队尾弹出
        // 因为它们比 nums[right] 小，且比 right 更旧，以后绝不会是最大值
        while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[right]) {
            deque.pollLast();
        }
        deque.addLast(right);
 
        // 步骤 2：清理队首。如果队首下标已不在窗口内（< right-k+1），弹出
        if (deque.peekFirst() <= right - k) {
            deque.pollFirst();
        }
 
        // 步骤 3：窗口已满（right >= k-1）时，队首就是当前窗口最大值
        if (right >= k - 1) {
            result[right - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

时间复杂度：$O(n)$，每个下标最多入队一次、出队一次（均摊 $O(1)$） 空间复杂度：$O(k)$（队列中最多 $k$ 个下标）

2.4 逐步追踪

以 nums = [1,3,-1,-3,5,3,6,7], k=3 追踪：

right=0, nums[0]=1: deque=[], 清理无，加入 0 → deque=[0]，未满
right=1, nums[1]=3: nums[0]=1<=3，弹出0，加入1 → deque=[1]，未满
right=2, nums[2]=-1: -1<3，直接加入2 → deque=[1,2]，满！result[0]=nums[1]=3 ✓
right=3, nums[3]=-3: -3<-1，加入3 → deque=[1,2,3]
  检查队首：1 <= 3-3=0？1 <= 0？否，队首保留
  result[1]=nums[1]=3 ✓
right=4, nums[4]=5: 5>-3弹出3，5>-1弹出2，5>3弹出1 → deque=[4]
  检查队首：4 <= 4-3=1？4 <= 1？否
  result[2]=nums[4]=5 ✓
right=5, nums[5]=3: 3<5，加入5 → deque=[4,5]
  检查队首：4 <= 5-3=2？4 <= 2？否
  result[3]=nums[4]=5 ✓
right=6, nums[6]=6: 6>3弹出5，6>5弹出4 → deque=[6]
  检查队首：6 <= 6-3=3？否
  result[4]=nums[6]=6 ✓
right=7, nums[7]=7: 7>6弹出6 → deque=[7]
  检查队首：7 <= 7-3=4？否
  result[5]=nums[7]=7 ✓

输出 [3,3,5,5,6,7] ✓

2.5 单调队列的正确性直觉

每次弹出队尾的”小元素”时，相当于说：“你已经被比你晚到但比你大的元素淘汰了，在你离开窗口之前，永远不会轮到你当最大值。“这个”提前淘汰”操作保证了队列的单调性，同时不会错过任何真正的最大值。

设计哲学：单调队列是懒惰删除的一种形式

单调队列不是把所有元素存起来再慢慢处理，而是”来了一个强者，弱者主动离场”。这种懒惰删除的思想在算法中非常常见——与其维护所有状态，不如在必要时提前清除已经无用的信息。

---

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

3.1 题目

LeetCode 1438 - Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit（中等）

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

输入：nums = [8,2,4,7], limit = 4
输出：2
解释：满足条件的子数组：[8,2]（差6，不满足）、[2,4]（差2，满足）、[4,7]（差3，满足）、[2,4,7]（差5，不满足）等。最长是 2。

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4，解释：满足条件的子数组 [2,4,7,2]，最大差 |7-2|=5 满足

3.2 合法性分析：需要同时维护最大值和最小值

“任意两个元素的绝对差 ≤ limit”，等价于”窗口内最大值 - 窗口内最小值 ≤ limit”（因为最大绝对差恰好等于最大值减最小值）。

合法条件：max(window) - min(window) <= limit

这需要同时维护窗口内的最大值和最小值。用两个单调队列：

• maxDeque：单调递减，队首是窗口最大值
• minDeque：单调递增，队首是窗口最小值

public int longestSubarray(int[] nums, int limit) {
    int n = nums.length;
    int left = 0, maxLen = 0;
    Deque<Integer> maxDeque = new ArrayDeque<>();  // 单调递减，维护最大值
    Deque<Integer> minDeque = new ArrayDeque<>();  // 单调递增，维护最小值
 
    for (int right = 0; right < n; right++) {
        // 进窗：维护 maxDeque（弹出尾部 <= nums[right] 的元素）
        while (!maxDeque.isEmpty() && nums[maxDeque.peekLast()] <= nums[right]) {
            maxDeque.pollLast();
        }
        maxDeque.addLast(right);
 
        // 进窗：维护 minDeque（弹出尾部 >= nums[right] 的元素）
        while (!minDeque.isEmpty() && nums[minDeque.peekLast()] >= nums[right]) {
            minDeque.pollLast();
        }
        minDeque.addLast(right);
 
        // 收缩：当最大值 - 最小值 > limit 时，从左边收缩
        while (nums[maxDeque.peekFirst()] - nums[minDeque.peekFirst()] > limit) {
            // 判断应该移动哪个元素：移动更旧的那个（下标更小的）
            left = Math.min(maxDeque.peekFirst(), minDeque.peekFirst()) + 1;
 
            // 清理过时的队首
            if (maxDeque.peekFirst() < left) maxDeque.pollFirst();
            if (minDeque.peekFirst() < left) minDeque.pollFirst();
        }
 
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

上面的收缩逻辑稍有些复杂。更清晰的写法：

public int longestSubarray(int[] nums, int limit) {
    int n = nums.length;
    int left = 0, maxLen = 0;
    Deque<Integer> maxQ = new ArrayDeque<>();
    Deque<Integer> minQ = new ArrayDeque<>();
 
    for (int right = 0; right < n; right++) {
        // 维护单调递减的 maxQ
        while (!maxQ.isEmpty() && nums[maxQ.peekLast()] < nums[right]) maxQ.pollLast();
        maxQ.addLast(right);
        // 注意：这里用 < 还是 <=？
        // 用 < 表示"弹出严格小于 nums[right] 的"，队列中可能有相等元素
        // 用 <= 表示"弹出 <= nums[right] 的"，队列中只有严格递减
        // 对于求最大值，两种都正确（队首仍是最大值）
 
        // 维护单调递增的 minQ
        while (!minQ.isEmpty() && nums[minQ.peekLast()] > nums[right]) minQ.pollLast();
        minQ.addLast(right);
 
        // 收缩左边界：当窗口不合法时
        while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > limit) {
            left++;
            if (maxQ.peekFirst() < left) maxQ.pollFirst();
            if (minQ.peekFirst() < left) minQ.pollFirst();
        }
 
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

时间复杂度：$O(n)$（每个元素各入队/出队各两个队列，均摊 $O(1)$） 空间复杂度：$O(n)$（最坏情况两个队列各 $n$ 个元素）

3.3 双单调队列的思维挑战

维护两个队列的难点是”两个队首同时维护”——合法性检查 max - min > limit 需要同时读两个队首，收缩时要弹出两个队首中下标更小的那个（更旧的元素）。这要求代码逻辑清晰，一步一步处理。

生产避坑：双队列的对称维护

maxQ 和 minQ 的维护逻辑方向相反（一个弹出”小于”，一个弹出”大于”），容易混淆。建议用注释明确标注每个队列的单调方向，以及弹出条件是 < 还是 <=（对于本题两者都正确，但在统计个数类题目中需要区分）。

---

第 4 章 LeetCode 2762：不间断子数组

4.1 题目

LeetCode 2762 - Continuous Subarrays（中等）

给你一个下标从 0 开始的整数数组 nums，nums 的一个子数组若满足以下条件则称之为不间断子数组：

• 子数组中任意一对元素 nums[i]、nums[j]（i <= j），都有 0 <= |nums[i] - nums[j]| <= 2

返回不间断子数组的总数目。

输入：nums = [5,4,2,4]
输出：8
解释：[5],[4],[2],[4],[5,4],[4,2],[2,4],[5,4,2,4]（注意：[5,4,2]不满足，|5-2|=3>2）

输入：nums = [1,2,3]
输出：6
解释：[1],[2],[3],[1,2],[2,3],[1,2,3]

4.2 与 1438 的对比：从最长到计数

1438 求满足条件的最长子数组，2762 求满足条件的所有子数组的数量。

合法条件与 1438 相同：max(window) - min(window) <= 2（把 limit 替换为 2）。

计数技巧：对于每个右端点 right，找到最长的合法窗口左端点 left（使得 [left, right] 合法），那么以 right 为右端点的合法子数组数量是 right - left + 1（子数组 [left,right], [left+1,right], ..., [right,right]，共 right-left+1 个）。

public long continuousSubarrays(int[] nums) {
    int n = nums.length;
    int left = 0;
    long count = 0;
    Deque<Integer> maxQ = new ArrayDeque<>();
    Deque<Integer> minQ = new ArrayDeque<>();
 
    for (int right = 0; right < n; right++) {
        // 维护单调递减的 maxQ
        while (!maxQ.isEmpty() && nums[maxQ.peekLast()] <= nums[right]) maxQ.pollLast();
        maxQ.addLast(right);
 
        // 维护单调递增的 minQ
        while (!minQ.isEmpty() && nums[minQ.peekLast()] >= nums[right]) minQ.pollLast();
        minQ.addLast(right);
 
        // 收缩左边界
        while (nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > 2) {
            left++;
            if (maxQ.peekFirst() < left) maxQ.pollFirst();
            if (minQ.peekFirst() < left) minQ.pollFirst();
        }
 
        // 以 right 为右端点的合法子数组数量
        count += right - left + 1;
    }
    return count;
}

时间复杂度：$O(n)$ 空间复杂度：$O(n)$

4.3 “个数累加”思维模式

可变窗口求最长/最短时，答案在每次窗口稳定后更新（取 max 或 min）。

可变窗口求个数时，对每个右端点 right，窗口 $[left,right]$ 合法后，以 right 为右端点的合法子数组有 right - left + 1 个，累加到答案中。

这个”个数 = 窗口长度”的推导是计数类滑动窗口的标准公式，第 09 篇还会深入讨论。

---

第 5 章 单调队列的本质与变体

5.1 单调队列与单调栈的关系

单调队列是单调栈的”两端版本”：

• 单调栈：只在一端（栈顶）出入，解决”下一个更大/更小元素”类问题
• 单调队列：在队尾入队、队尾/队首出队，多了队首出队（过期元素的清理），用于滑动窗口极值

两者都利用单调性提前淘汰无用元素，均摊 $O(1)$。

数据结构	出入端	典型应用
单调栈（递减）	从顶入/出	下一个更大元素
单调队列（递减）	从尾入，从尾/首出	滑动窗口最大值

5.2 TreeMap 作为单调队列的替代品

对于元素值范围较小的场景，TreeMap<Integer, Integer>（维护窗口内每种值的频率）是单调队列的替代方案：

TreeMap<Integer, Integer> tm = new TreeMap<>();
// 进窗
tm.merge(nums[right], 1, Integer::sum);
// 出窗
int v = nums[left];
if (tm.merge(v, -1, Integer::sum) == 0) tm.remove(v);
// 查最大/最小
int max = tm.lastKey();
int min = tm.firstKey();

TreeMap 的优点是代码直观；缺点是每次操作 $O(\log k)$，总体 $O(n\log k)$，比单调队列的 $O(n)$ 慢。对于大多数 LeetCode 题目，两者都能通过，但面试中能说出 $O(n)$ 解法更加分。

5.3 单调队列的适用范围

场景	适用性
固定窗口求最大/最小值	✅ 最典型用法（LeetCode 239）
可变窗口合法性涉及最大/最小值	✅（LeetCode 1438、2762）
需要同时维护最大和最小	✅ 两个队列各维护一个
需要第 k 大的元素	❌ 单调队列不支持，需要堆或 TreeMap
需要中位数	❌ 需要两个堆

---

本篇总结

本篇围绕单调队列，深度解析了固定/可变窗口中维护极值的 $O(n)$ 技法：

1. 单调队列的设计动机：提前淘汰”比新元素小且比新元素旧”的无用元素，均摊 $O(1)$ 维护窗口极值
2. LeetCode 239：固定窗口最大值，单调队列的入门题
3. LeetCode 1438：可变窗口最大值 + 最小值，两个单调队列同时维护
4. LeetCode 2762：可变窗口 + 计数，count += right - left + 1 的计数公式

核心结论：当窗口合法性涉及”窗口内最大/最小值”时，引入单调队列是标准解法，能将 $O(nk)$ 降至 $O(n)$。

---

参考与延伸

• 01 滑动窗口算法原理全景：从暴力枚举到 O(n) 的思维跃迁 — 极值维护困境的来源
• 09 多类别元素与恰好 K 型窗口：高阶滑动窗口技法 — 计数类窗口的进阶应用

---

课后练习

LeetCode 862 - 和至少为 K 的最短子数组（困难）

给你一个整数数组 nums（可含负数）和整数 k，找和至少为 k 的最短子数组，返回其长度；不存在则返回 -1。

提示：有负数，不能直接用滑动窗口（单调性被破坏）。用前缀和 + 单调双端队列：构建前缀和数组 P，转化为「找最短 [l, r] 使 P[r+1] - P[l] >= k」。用单调递增队列维护 P[l] 的候选；遍历 r+1 时，若 P[r+1] - P[队首] >= k 则更新答案并弹出队首；同时弹出队尾中 >= P[r+1] 的下标。这是单调队列与前缀和的综合进阶应用。