算法刷题系列（四十三）：单调队列——维护滑动区间中的极值

算法刷题系列（四十三）：单调队列——维护滑动区间中的极值

给定数组和窗口宽度 k，求每个长度为 k 的连续窗口最大值。每个窗口若重新扫描 k 个元素，复杂度是 O(nk)。单调双端队列（deque）通过丢弃已过期或已被支配的候选，把所有窗口的查询总成本降到 O(n)。

示例：[1, 3, -1, -3, 5, 3, 6, 7]，窗口宽度为 3，最大值依次是 [3, 3, 5, 5, 6, 7]。

队列维护什么

队列保存数组索引，并满足：

• 索引从队首到队尾递增；
• 对应值从队首到队尾递减；
• 队首是当前窗口最大值。

处理索引 i 时，先移除队首所有 < i - k + 1 的过期索引；再从队尾移除值 <= values[i] 的索引。新值更大或相等且更靠右，将来至少和旧值一样有用、并且过期更晚。最后把 i 入队。窗口完整后，队首就是最大值。

不变量：每个队列索引属于当前窗口，且队首的值不小于任何其后的候选。队尾弹出的元素被新元素支配，之后的窗口不可能再需要它。

Java 实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static int[] slidingWindowMaximum(int[] values, int k) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        if (k <= 0 || k > values.length) {
            if (values.length == 0 && k == 0) return new int[0];
            throw new IllegalArgumentException("k must be in [1, n]");
        }
        Deque<Integer> deque = new ArrayDeque<>();
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < values.length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() <= i - k) deque.removeFirst();
            while (!deque.isEmpty() && values[deque.peekLast()] <= values[i]) deque.removeLast();
            deque.addLast(i);
            if (i >= k - 1) result.add(values[deque.peekFirst()]);
        }
        int[] answer = new int[result.size()];
        for (int i = 0; i < answer.length; i++) answer[i] = result.get(i);
        return answer;
    }

    public static void main(String[] args) {
        int[] values = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(java.util.Arrays.toString(slidingWindowMaximum(values, 3)));
        // [3, 3, 5, 5, 6, 7]
    }
}

Python 实现

from collections import deque

def sliding_window_maximum(values: list[int], k: int) -> list[int]:
    if values is None:
        raise ValueError("values must not be None")
    if not values and k == 0:
        return []
    if not 1 <= k <= len(values):
        raise ValueError("k must be in [1, n]")
    candidates: deque[int] = deque()
    answer: list[int] = []
    for i, value in enumerate(values):
        while candidates and candidates[0] <= i - k:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(i)
        if i >= k - 1:
            answer.append(values[candidates[0]])
    return answer

assert sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert sliding_window_maximum([2, 2, 2], 1) == [2, 2, 2]
assert sliding_window_maximum([4], 1) == [4]
assert sliding_window_maximum([], 0) == []

复杂度、边界与错误排查

每个索引至多入队、出队一次，时间复杂度 O(n)，队列最坏保存 k 个索引，额外空间 O(k)。k 通常要求在 [1,n]；上面为了定义空输入行为，特意约定空数组且 k=0 返回空结果，其余非法窗口抛错。

务必存索引而不是只存值，否则遇到重复最大值时无法判断哪个已离开窗口。过期条件 index <= i - k 与 index < i - k + 1 等价，错一位会造成旧值留在窗口。若求最小值，将队列对应值改为递增：从队尾弹出 >= 当前值。需要保留相等元素的先后次序时，可调整比较符号，但最大值结果不变。

小结

单调队列同时用两端删除：队首清除过期索引，队尾清除被新值支配的候选。保留索引可准确处理窗口边界，这种结构也常用于约束长度的 DP 转移和区间最值查询。