寻求列表中子列表元素最大值的最优实现方法

你当前的暴力实现时间复杂度为 O(n·k)（k 为窗口大小），在数组规模较大时效率不足。下面提供基于单调队列的线性时间解法，能将时间复杂度优化至 O(n)。

核心原理 #

维护一个存储数组索引的单调递减队列，确保队列头部始终是当前窗口内最大值的索引：

• 遍历数组时，先移除队列中超出当前窗口范围的索引
• 再移除队列中所有值小于当前元素的索引（这些元素无法成为后续窗口的最大值）
• 将当前元素的索引加入队列
• 当遍历到对应位置后，队列头部的元素即为当前窗口的最大值

适配需求的实现代码 #

针对你需求中「每个位置取左右各 span/2 范围内元素最大值」的逻辑，以下是完整的 O(n) 实现：

#include <vector>
#include <deque>
#include <iostream>
using namespace std;

vector<int> movMax(const vector<int>& v, int span) {
    int half = span / 2;
    int n = v.size();
    vector<int> ret(n);
    deque<int> idxDeque; // 存储索引，对应元素单调递减

    // 第一阶段：遍历数组，维护单调队列并处理前半部分位置的最大值
    for (int i = 0; i < n; ++i) {
        // 移除队列中比当前元素小的索引，保证队列递减
        while (!idxDeque.empty() && v[idxDeque.back()] <= v[i]) {
            idxDeque.pop_back();
        }
        idxDeque.push_back(i);

        // 当遍历到可以覆盖位置 j = i - half 的窗口右边界时，记录最大值
        if (i >= half) {
            int j = i - half;
            // 移除超出当前窗口左边界的索引
            while (!idxDeque.empty() && idxDeque.front() < max(0, j - half)) {
                idxDeque.pop_front();
            }
            ret[j] = v[idxDeque.front()];
        }
    }

    // 第二阶段：处理数组末尾无法在第一阶段覆盖的位置
    for (int j = n - half; j < n; ++j) {
        while (!idxDeque.empty() && idxDeque.front() < max(0, j - half)) {
            idxDeque.pop_front();
        }
        ret[j] = v[idxDeque.front()];
    }

    return ret;
}

int main() {
    vector<int> v = {4, 3, 3, 7, 2, 5, 1, 2};
    v = movMax(v, 3);
    for (int x : v) {
        cout << x << ' '; // 输出：4 4 7 7 7 5 5 2
    }
    cout << endl;
    return 0;
}

复杂度说明 #

• 时间复杂度：O(n)，每个元素最多入队和出队各一次，总操作次数与数组长度线性相关
• 空间复杂度：O(k)，k 为窗口最大尺寸（即 span + 1），队列最多存储 k 个索引

相较于你的暴力实现，该解法在处理大规模数组时性能提升极为明显，例如当数组长度为 1e6 时，暴力解法会因 O(n·k) 的复杂度陷入卡顿，而线性时间解法能快速完成计算。

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