面试题59（一）：滑动窗口的最大值

用保存候选下标的单调双端队列，在队尾淘汰被支配值、在队首移除过期值。

学习目标

  • 能用单调双端队列在 O(n) 时间求滑动窗口最大值
  • 能解释"队尾淘汰被支配值、队首移除过期值"的双端队列操作
  • 能处理窗口大小大于数组长度等边界

从“每个窗口都重新扫描吗”开始

先预测：数组2、3、4、2、6、2、5、1，窗口大小3，共有6个窗口。若每次扫描3个值取最大，时间O(nk)；当窗口接近数组长度时会接近O(n平方)。

窗口右移时，大部分元素仍然保留。真正需要跟踪的不是全部窗口成员，而是仍有机会成为当前或未来最大值的。

单调队列：队首到队尾值递减，队首即窗口最大窗口 [2, 4]（size=3）2031422364255617max=6单调双端队列（下标:值，队首→队尾递减）[4:6]队首队尾队尾淘汰：新值 ≥ 队尾值 → 弹出队尾（更早且更小，永不优先）队首过期：队首下标 ≤ i-size → 弹出队首（已离开窗口）输出：num[队首] 即窗口最大值（本窗口 4,4,6,6,6,5）每个下标入队一次、出队至多一次，O(n) 摊还；队列空间 O(size)。
双端队列保存仍可能成为当前或未来窗口最大值的候选下标。

作者用双端队列保存这些下标。下标从队首到队尾递增，对应数组值则，所以队首下标对应当前滑动窗口的最大值。

分步1 / 3

队尾淘汰被支配值

新元素更大时，队尾旧值被淘汰，因为不再可能成为最大值。

单调队列：队首到队尾值递减，队首即窗口最大窗口 [2, 4]（size=3）2031422364255617max=6单调双端队列（下标:值，队首→队尾递减）[4:6]队首队尾队尾淘汰：新值 ≥ 队尾值 → 弹出队尾（更早且更小，永不优先）队首过期：队首下标 ≤ i-size → 弹出队首（已离开窗口）输出：num[队首] 即窗口最大值（本窗口 4,4,6,6,6,5）每个下标入队一次、出队至多一次，O(n) 摊还；队列空间 O(size)。
双端队列保存仍可能成为当前或未来窗口最大值的候选下标。

为什么较小的旧值永远失去资格（）

新值num[i]到来时，若它大于或等于队尾候选值，旧队尾同时满足“值不更大”和“出现更早”：

  1. 在两个下标共同存在的窗口中，新值至少一样大。
  2. 窗口继续右移时，旧值会先过期，新值活得更久。

旧队尾此后不可能优先成为最大值，可以永久弹出。持续删除直到队尾值严格大于新值，再把i压入。这称为。

过期是另一回事。新窗口左边界为i减size加1，任何下标不大于i减size都已离窗。若这样的下标位于队首，必须从前端删除，称为。

条件事实结论动作
新值大于等于队尾值队尾更早且不更大未来窗口永远不会优先从队尾弹出
队首下标不大于 i-size已离开新窗口即使值最大也失效从队首弹出
其余候选下标递增、值递减各有可能在前者过期后接任保留
完成窗口队首仍在窗内且值最大直接读取 num[index.front]输出
队尾按值淘汰，队首按时间过期；两种删除解决不同问题。

队尾按值删除，队首按时间删除。只实现其中一种都不够。

忠实还原作者两阶段循环

作者先单独处理前size个元素，建立第一个窗口的候选队列；随后每读一个新下标，先输出上一窗口最大值，再更新队列；循环结束后补最后一个窗口。

#include <deque>
#include <vector>
 
std::vector<int> maxInWindows(
    const std::vector<int>& num,
    unsigned int size) {
    std::vector<int> result;
    if (num.size() >= size &&
        size >= 1) {
        std::deque<int> index;
 
        for (unsigned int i = 0;
             i < size;
             ++i) {
            while (!index.empty() &&
                   num[i] >=
                       num[index.back()]) {
                index.pop_back();
            }
            index.push_back(i);
        }
 
        for (unsigned int i = size;
             i < num.size();
             ++i) {
            result.push_back(
                num[index.front()]);
 
            while (!index.empty() &&
                   num[i] >=
                       num[index.back()]) {
                index.pop_back();
            }
            if (!index.empty() &&
                index.front() <=
                    static_cast<int>(
                        i - size)) {
                index.pop_front();
            }
            index.push_back(i);
        }
        result.push_back(
            num[index.front()]);
    }
    return result;
}

合法条件是size至少1且不超过数组长度。窗口数为n减size加1，因此最后一次补输出不可遗漏。

作者示例的完整队列轨迹

对2、3、4、2、6、2、5、1和size为3：

  • 2入队；3淘汰2；4淘汰3，首窗队列只剩下标2，对应最大值4。
  • 新2不能淘汰4，队列为2、3，下一个窗口仍输出4。
  • 新6从队尾依次淘汰2和4，只剩下标4，窗口最大值6。
  • 新2保留在6之后；新5淘汰2但保留6。
  • 新1到来时，下标4的6已经过期，从队首移除，5成为最后窗口最大值。

输出依次4、4、6、6、6、5，与作者Test1一致。

相等值为何淘汰旧下标

源码条件使用大于等于，因此新值与队尾相等时也删除旧下标，只保留更晚出现的同值。新下标值相同但过期更晚，完全支配旧下标。

若只使用大于而保留相等值，算法仍可正确，但队列可能保存多个相同候选，需要依靠队首逐个过期。作者策略让队列更紧凑并保持值严格递减。

不能把大于等于误改为从队首删除。被新值支配的是队尾较小候选；队首可能仍比新值大，是当前最大值。

为什么必须保存

下标还让输出无需复制窗口成员。队列最多保存size个候选，空间O(size)，不随值域大小变化。

作者使用保存int下标的deque，却以unsigned int遍历vector。普通规模下转换正常；若元素数超过INT_MAX，把大下标压入int会失真。现代版应统一使用size_t。

统一单循环模板

可以把首窗和后续窗口合成一个循环：每次先淘汰队尾、压入新下标，再移除过期队首；当i加1至少为size时输出队首。

#include <cstddef>
#include <deque>
#include <span>
#include <vector>
 
std::vector<int> maxInWindowsUnified(
    std::span<const int> values,
    std::size_t size) {
    std::vector<int> result;
    if (size == 0 ||
        size > values.size()) {
        return result;
    }
 
    std::deque<std::size_t> candidates;
    result.reserve(
        values.size() - size + 1);
 
    for (std::size_t i = 0;
         i < values.size();
         ++i) {
        while (!candidates.empty() &&
               values[i] >=
                   values[candidates.back()]) {
            candidates.pop_back();
        }
        candidates.push_back(i);
 
        const std::size_t windowStart =
            i + 1 >= size
                ? i + 1 - size
                : 0;
        while (!candidates.empty() &&
               candidates.front()
                   < windowStart) {
            candidates.pop_front();
        }
 
        if (i + 1 >= size) {
            result.push_back(
                values[candidates.front()]);
        }
    }
    return result;
}

这个版本更新当前窗口后再输出，与作者“先输出上一窗再加入新值”的时序不同，但结果等价。实现时必须选定一种时序，不能把过期公式和输出位置从两个模板拼在一起。

正确性不变式

处理到下标i后，队列满足三条不变式：

  1. 所有下标严格递增，并位于当前窗口范围内。
  2. 对应值从队首到队尾严格递减。
  3. 窗口内任何未在队列中的元素，都被一个更晚且不小的候选支配。

因此队首既未过期，又不小于所有保留候选；被删元素也不可能更优，队首就是最大值。

新元素入队时从队尾删除被支配项，保持第二、三条；按左边界移除队首，保持第一条；其余候选相对顺序不变。由归纳，每次输出正确。

O(n)来自摊还而非每轮常数

某个特别大的新值可能一次弹出许多队尾，单轮看似O(size)。但每个下标只入队一次，被队尾淘汰或队首过期后就永不回来，整个运行中弹出总次数不超过n。

这种把偶尔昂贵操作分摊到所有元素上的证明称为。总时间O(n)，队列空间O(size)。

与优先队列相比，堆可在O(log size)插入并延迟删除过期值，适用于更一般优先级场景；本题利用窗口按时间滑动和只查最大值，单调队列更直接。

“队首过期与队尾淘汰”必须按各自条件独立理解。一个候选可能因为时间最早而从队首离开，也可能在尚未过期时被更晚大值从队尾支配；无论走哪条路径，它只会出队一次。正是这两个互斥出口让总删除次数可计数，而不是假设每轮while只执行一次。

该结构也适合在线数据流。每到一个新样本即可更新候选并在首个完整窗口后立刻输出，不必等待全部数组。若历史数组不可随机访问，队列节点应同时保存下标和值，过期仍看下标、单调比较直接看值；内存仍不超过窗口候选数量。流被分片时则要谨慎，窗口可能跨分片边界，不能独立计算后只拼接最大值，必须把边界候选状态一并传递或保留重叠数据。

固定窗口大小让左边界每步只前进一格。若窗口大小随时间变化但左边界仍单调右移，同一队列仍可按实际windowStart清理；若窗口突然向左扩张，之前已淘汰或过期的元素无法恢复，必须保存更多历史或重建。单调队列支持的是单向时间窗口，不是任意区间查询。

把队尾比较方向反转即可维护窗口最小值；若同时需要最大与最小，可维护两个deque，各自O(n)摊还和O(size)空间。若还要中位数或任意分位数，单调队列不再携带足够顺序统计信息，需要双堆、平衡树或计数结构。

边界输入与输出数量

维度作者契约或不变式结论边界
合法窗口1 到数组长度输出 n-size+1 个否则返回空
队列内容候选元素下标可判断过期只存值不够
值顺序从队首到队尾严格递减队首即最大值相等时保留较新下标
下标顺序严格递增队首最早过期每步最多一个旧边界
复杂度每个下标入队一次、出队至多一次O(n) 摊还队列空间 O(size)
索引类型源码 deque<int>普通规模可用超大 vector 应用 size_t
单调队列同时编码候选优先级与过期时间，合法窗口才产生结果。

size为1时每个单元素窗口最大值就是自身，输出原数组。size等于n时只有一个窗口，输出全局最大值。

对任意合法size，输出数量必须精确等于n减size加1。这个性质与具体最大值无关，能单独抓出漏补最后窗口、过早输出首窗或多输出未满窗口等时序错误。返回空vector时则要结合输入判断：可能是数组空、size为0或size过大，而不是“存在合法窗口但最大值为空”。

size为0、size大于n或数组为空时作者返回空vector，不区分三种无效原因。若API需要诊断，可返回expected或错误枚举。

不存在数值溢出，因为算法只比较和复制int，不做加法。但索引差i减size必须在确认i不小于size的阶段执行；作者只在第二个循环i从size开始，避免unsigned下溢。

作者9组测试逐项还原

  1. 书中综合示例，size3，输出4、4、6、6、6、5。
  2. 1、3、-1、-3、5、3、6、7，size3，输出3、3、5、5、6、7。
  3. 单调递增数组，size4，最大值始终是新右端。
  4. 单调递减数组，size5，最大值依次由旧队首过期交接。
  5. size为1，输出与输入完全相同。
  6. size等于数组长度，输出单个全局最大值14。
  7. size为0，输出空。
  8. size大于数组长度，输出空。
  9. 空数组配size5，输出空。

作者Test逐元素比较result与expected，并要求两个迭代器同时到达末尾，因此既检查值，也检查输出长度。

#include <algorithm>
#include <cassert>
#include <vector>
 
std::vector<int> bruteWindowMax(
    const std::vector<int>& values,
    std::size_t size) {
    std::vector<int> result;
    if (size == 0 ||
        size > values.size()) {
        return result;
    }
    for (std::size_t start = 0;
         start + size <= values.size();
         ++start) {
        result.push_back(
            *std::max_element(
                values.begin() + start,
                values.begin()
                    + start + size));
    }
    return result;
}
 
void testWindowMax() {
    const std::vector<int> values{
        2, 3, 4, 2, 6, 2, 5, 1};
    assert(maxInWindows(values, 3)
           == std::vector<int>{
               4, 4, 6, 6, 6, 5});
    assert(maxInWindows(values, 1)
           == values);
    assert(maxInWindows(values, 0)
           .empty());
    assert(maxInWindows(values, 9)
           .empty());
    assert(maxInWindows(values, 3)
           == bruteWindowMax(values, 3));
}

随机对拍可生成含重复、负数、递增、递减和锯齿数据，对每个合法size与朴素扫描比较。还应断言输出数量恰为n减size加1。

若实现TypeScript版本，普通数组shift会搬移后续元素，单次O(size)，破坏线性保证。应使用真正双端队列库、环形缓冲区，或用头指针避免前端搬移并定期压缩存储。

本章练习

练习

问题 1： 双端队列为什么能做到 O(n)？

问题 2： 队尾淘汰和队首过期的条件各是什么？

问题 3： 窗口大小大于数组长度时返回什么？

概念说明

本章核心概念包括：保存候选元素下标。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 滑动窗口的最大值由保存候选元素下标的双端队列维护。
  2. 队列下标递增，对应值单调递减，队首就是最大值。
  3. 新值从队尾淘汰更小或相等旧值，保留更晚候选。
  4. 队首过期按新窗口左边界删除，必须保存下标。
  5. 作者先构造首窗，再先输出旧窗、处理新值、最后补一次。
  6. 统一单循环可先更新新窗再输出，但时序公式不能混用。
  7. 每个下标至多入队、出队一次，摊还时间O(n)、空间O(size)。
  8. 作者9组测试覆盖综合序列、单调数据和所有窗口边界。

名词解释

名词解释

本章出现的专业名词，用大白话再讲一遍。

候选
仍有可能成为窗口最大值的元素下标。
支配
新值更大时，旧值被淘汰，因为旧值不再可能成为最大值。
下标
元素在数组中的位置，用于判断是否过期。
复习本章（5 题）

讨论

评论区加载中…