如何优化计算数组滑动窗口最大值的C++函数性能？

这个问题我之前做性能调优的时候碰到过！原来的暴力实现每次都调用std::max_element扫整个窗口，当period很大（比如接近数组长度）的时候，性能会暴跌——毕竟时间复杂度是O(n*period)，做了超多重复计算。下面给你几个从易到难的优化方向：

1. 先处理边界特殊情况 #

先把最基础的特殊情况挡在外面，避免做无用功：

• 如果period == 0或者输入数组v为空，直接把vv清空即可；
• 如果period == 1，每个窗口就是单个元素，直接vv = v复制数组就行，完全不用跑后续的循环逻辑。

代码里可以先加这段判断：

if (v.empty() || period == 0) {
    vv.clear();
    return;
}
if (period == 1) {
    vv = v;
    return;
}

2. 核心优化：用单调队列将时间复杂度降到O(n) #

这是性能提升最明显的方案，用单调递减队列（借助std::deque实现）来维护窗口内的最大值候选。队列里存储的是数组元素的索引，保证队列头部始终是当前窗口最大值的索引，队列内的索引对应的数值是单调递减的。

具体逻辑步骤：

• 遍历数组的每个元素（索引i从0开始）：
  1. 移除队列头部那些已经不在当前窗口范围内的索引（窗口是左闭右开区间[i-period, i)，所以索引小于i-period的都要弹出）；
  2. 从队列尾部开始，把所有对应数值小于当前元素v[i]的索引都弹出——这些元素不可能成为后续任何窗口的最大值了，直接淘汰；
  3. 将当前索引i加入队列尾部；
  4. 当i >= period - 1时（第一个窗口形成之后），队列头部的索引对应的数值就是当前窗口的最大值，把它存入vv[i]（和原代码的输出逻辑完全对齐）。

优化后的完整代码：

#include <deque>
#include <vector>

void f(const std::vector<double> &v, std::vector<double> &vv, size_t period) {
    // 边界处理
    if (v.empty() || period == 0) {
        vv.clear();
        return;
    }
    if (period == 1) {
        vv = v;
        return;
    }

    const size_t n = v.size();
    vv.resize(n);
    std::deque<size_t> max_deque;

    for (size_t i = 0; i < n; ++i) {
        // 移除窗口外的无效索引
        while (!max_deque.empty() && max_deque.front() < i - period) {
            max_deque.pop_front();
        }
        // 移除队列尾部比当前元素小的元素，维护单调递减性
        while (!max_deque.empty() && v[i] >= v[max_deque.back()]) {
            max_deque.pop_back();
        }
        max_deque.push_back(i);

        // 窗口形成后，记录最大值（和原代码输出逻辑一致）
        if (i >= period - 1) {
            vv[i] = v[max_deque.front()];
        }
    }
}

3. 其他小优化点 #

• 减少内存分配：如果调用方能保证vv的大小已经等于v.size()，可以跳过resize操作，减少内存开销；
• 编译器优化：开启O2/O3级别的编译优化（比如GCC的-O3），编译器会对循环做自动向量化、指令重排等优化，配合单调队列的代码，性能会更上一层楼；
• 避免迭代器计算：原代码中v.begin() + i - period这种迭代器偏移，换成直接用索引访问v[i]会更直观且略快。

性能对比 #

举个直观的例子：如果数组长度是1e6，period是1000，暴力法需要做1e9次元素比较，而单调队列只需要1e6次左右的操作，性能差距能达到几百倍甚至上千倍。

内容的提问来源于stack exchange，提问作者Ufx