能否用C++的std::max查找子数组最大值？求可行实现方法

关于std::max的可行性 #

你用的std::max是仅能比较两个单个值的版本，而代码里arr+k是指针（指向数组第k个元素的位置），和result（单个int值）无法直接比较，所以会出错。但可以用C++标准库的std::max_element函数实现需求——它专门用来查找指定范围内的最大值，需要包含<algorithm>头文件。

修正后的std::max_element实现代码 #

#include <vector>
#include <algorithm> // 必须包含该头文件

std::vector<int> max_of_subarrays(int *arr, int n, int k) {
    std::vector<int> v;
    for (int i = 0; i <= n - k; ++i) {
        // 查找arr[i]到arr[i+k-1]范围内的最大值
        int* max_ptr = std::max_element(arr + i, arr + i + k);
        v.push_back(*max_ptr);
    }
    return v;
}

比如数组{1,2,3,4,5}、k=2时，输出就是{2,3,4,5}，符合预期。

其他实现方法 #

1. 暴力遍历法 #

最直观的思路，对每个窗口嵌套遍历找最大值，代码简单但时间复杂度为O(nk)，数据量大时效率较低：

std::vector<int> max_of_subarrays(int *arr, int n, int k) {
    std::vector<int> v;
    for (int i = 0; i <= n - k; ++i) {
        int current_max = arr[i];
        for (int j = i + 1; j < i + k; ++j) {
            if (arr[j] > current_max) {
                current_max = arr[j];
            }
        }
        v.push_back(current_max);
    }
    return v;
}

2. 滑动窗口+双端队列（最优时间复杂度） #

用双端队列维护当前窗口内可能成为最大值的元素索引，保证队列头部始终是当前窗口的最大值索引，时间复杂度为O(n)：

#include <vector>
#include <deque>

std::vector<int> max_of_subarrays(int *arr, int n, int k) {
    std::vector<int> v;
    std::deque<int> dq; // 存储数组索引，对应元素单调递减

    for (int i = 0; i < n; ++i) {
        // 移除队列中不在当前窗口内的索引（窗口范围为[i-k+1, i]）
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // 移除队列尾部所有比当前元素小的索引，它们不可能成为后续窗口的最大值
        while (!dq.empty() && arr[i] >= arr[dq.back()]) {
            dq.pop_back();
        }
        dq.push_back(i);

        // 遍历到第k-1个元素时，开始记录每个窗口的最大值
        if (i >= k - 1) {
            v.push_back(arr[dq.front()]);
        }
    }
    return v;
}

3. 分块预处理法 #

通过预处理两个辅助数组，实现O(n)时间复杂度查找：

• left数组：left[i]表示从块起始位置到i的最大值
• right数组：right[i]表示从i到块结束位置的最大值

#include <vector>
#include <algorithm>

std::vector<int> max_of_subarrays(int *arr, int n, int k) {
    std::vector<int> v;
    std::vector<int> left(n);
    std::vector<int> right(n);

    // 填充left数组
    for (int i = 0; i < n; ++i) {
        if (i % k == 0) {
            left[i] = arr[i];
        } else {
            left[i] = std::max(left[i-1], arr[i]);
        }
    }

    // 填充right数组
    right[n-1] = arr[n-1];
    for (int i = n-2; i >= 0; --i) {
        if ((i+1) % k == 0) {
            right[i] = arr[i];
        } else {
            right[i] = std::max(right[i+1], arr[i]);
        }
    }

    // 计算每个窗口的最大值
    for (int i = 0; i <= n - k; ++i) {
        int j = i + k - 1;
        if (i % k == 0) {
            v.push_back(right[i]);
        } else {
            v.push_back(std::max(left[j], right[i]));
        }
    }
    return v;
}

内容的提问来源于stack exchange，提问作者Krishna Nand Yadav