单调队列：滑动窗口最值

问题#

给定长度为 $n$ 的数组和窗口长度 $k$。窗口从左到右每次移动一格，求每个长度为 $k$ 的窗口中的最大值。

逐个窗口扫描需要 $O(nk)$ 时间。我们真正需要保存的并不是窗口中的所有元素，而是 仍有机会成为当前或未来最大值的候选。

核心思想#

双端队列中保存候选元素的下标。处理位置 $i$ 时依次完成：

1. 从队首删除已经离开窗口的下标。
2. 从队尾删除值小于等于 $a_i$ 的下标。
3. 把 $i$ 放到队尾。
4. 当第一个完整窗口形成后，队首就是窗口最大值的下标。

第二步为何安全？若旧下标 $j<i$ 且 $a_j\le a_i$，那么 $i$ 更晚离开窗口，值又 不小于 $a_j$。从现在开始，$j$ 永远不可能比 $i$ 更适合作为最大值。

不变量#

• 队列中的下标严格递增。
• 队列中的下标都位于当前窗口。
• 队列中对应的值严格递减，因此队首始终是最大值。

模板在值相等时删除旧下标、保留新下标。这样不会改变最大值，并能让候选存活更久。

复杂度#

每个下标最多从队尾进入一次，并从队首或队尾离开一次：

• 时间：$O(n)$
• 额外空间：$O(k)$

可独立编译的 C++17 模板#

输入第一行是 $n,k$，第二行是数组。约定 $1\le k\le n$；不满足时程序不输出结果。

#include <cstddef>
#include <deque>
#include <iostream>
#include <vector>

std::vector<long long> sliding_window_maximum(
    const std::vector<long long>& values,
    int window_size
) {
    const int n = static_cast<int>(values.size());
    if (window_size <= 0 || window_size > n) {
        return {};
    }

    std::deque<int> candidates;
    std::vector<long long> answer;
    answer.reserve(
        static_cast<std::size_t>(n - window_size + 1)
    );

    for (int i = 0; i < n; ++i) {
        const int first_valid = i - window_size + 1;
        while (
            !candidates.empty() &&
            candidates.front() < first_valid
        ) {
            candidates.pop_front();
        }

        while (
            !candidates.empty() &&
            values[static_cast<std::size_t>(candidates.back())] <=
                values[static_cast<std::size_t>(i)]
        ) {
            candidates.pop_back();
        }

        candidates.push_back(i);
        if (i + 1 >= window_size) {
            answer.push_back(
                values[static_cast<std::size_t>(candidates.front())]
            );
        }
    }

    return answer;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n = 0;
    int window_size = 0;
    std::cin >> n >> window_size;
    if (n < 0) {
        return 0;
    }

    std::vector<long long> values(static_cast<std::size_t>(n));
    for (long long& value : values) {
        std::cin >> value;
    }

    const std::vector<long long> answer =
        sliding_window_maximum(values, window_size);
    for (std::size_t i = 0; i < answer.size(); ++i) {
        if (i != 0) {
            std::cout << ' ';
        }
        std::cout << answer[i];
    }
    std::cout << '\n';
}

示例#

输入：

8 3
1 3 -1 -3 5 3 6 7

输出：

3 3 5 5 6 7

例如窗口 $[-1,-3,5]$ 形成时，旧候选 $-1,-3$ 都会从队尾删除，队首直接变成 5。

易错点#

• 队列中保存值：仅保存值无法判断它何时离开窗口，必须保存下标。
• 过期条件差一位：对当前右端 $i$，合法窗口左端是 $i-k+1$，下标小于它才 过期。
• 过早输出：只有 $i+1\ge k$ 时才形成完整窗口。
• 重复值处理不一致：弹出小于等于当前值会保留更新的下标；只弹出小于也正确，但 队列可能保留更多相等元素。
• 最大值与最小值方向写反：求最大值维护递减队列，求最小值维护递增队列。
• 把双端队列误写成普通队列：候选既可能从队首过期，也可能从队尾被淘汰。

边界测试#

• $k=1$：答案应与原数组相同。
• $k=n$：只输出全局最大值。
• 严格递增、严格递减、全部相等。
• 最大值重复出现，旧最大值恰好离开窗口。
• 全负数与单元素数组。
• 非法 $k=0$ 或 $k>n$ 是否按接口约定处理。
• 随机短数组，与每个窗口直接调用最大值函数的 $O(nk)$ 实现对拍。

变体#

• 滑动窗口最小值：把队尾比较改为大于等于当前值。
• 同时求最大和最小：分别维护一个递减队列与一个递增队列。
• 不定长窗口：只要窗口左端单调右移，仍可按相同规则删除过期下标。
• DP 优化：当转移只依赖一个滑动区间内的最优值时，单调队列可把一次转移从 $O(k)$ 降到均摊 $O(1)$。
• 延伸阅读（非课程主线）：二维滑动窗口：先对每行做一次，再对中间结果的每列 做一次。