T20828 tijie

Kenny

2024-05-02 16:04:21

发布于：广东

21阅读

0回复

0点赞

滑动窗口最大值 - C++ 题解 (暴力解法优化)

虽然题目要求使用暴力解法，但我们仍然可以进行一些优化，以降低时间复杂度。

思路：

遍历每个窗口： 对于每个窗口起始位置，遍历窗口内的所有元素，找到最大值。
优化搜索范围： 利用已知信息减少不必要的比较次数。

C++ 代码实现：

#include <iostream>
#include <vector>

using namespace std;

vector<int> max_sliding_window(const vector<int>& nums, int k) {
    vector<int> result;
    int n = nums.size();

    for (int i = 0; i <= n - k; ++i) {
        int max_val = nums[i]; // 将窗口第一个元素设为初始最大值
        
        // 从窗口第二个元素开始遍历，与当前最大值比较
        for (int j = i + 1; j < i + k; ++j) {
            if (nums[j] > max_val) {
                max_val = nums[j];
                // 如果找到更大的元素，且该元素位置距离窗口结束不足 k，则无需继续遍历
                if (j <= n - k) break; 
            }
        }

        result.push_back(max_val);
    }

    return result;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    vector<int> result = max_sliding_window(nums, k);
    for (int x : result) {
        cout << x << " ";
    }
    cout << endl;

    return 0;

}