T20828 tijie

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

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

思路：

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

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;

}

代码解释：

• 使用两层循环遍历每个窗口。
• 外层循环遍历窗口起始位置。
• 内层循环遍历窗口内元素，找到最大值。
• 优化：
  • 将窗口第一个元素设为初始最大值，减少一次比较。
  • 如果找到更大的元素，且该元素位置距离窗口结束不足 k，则说明该元素一定会出现在后续窗口中，无需继续遍历当前窗口。

复杂度分析：

• 最坏情况下，每个窗口都需要遍历 k 个元素，时间复杂度为 O(nk)。
• 最好情况下，第一个元素就是最大值，且后续元素都小于它，时间复杂度为 O(n)。
• 平均情况下，时间复杂度介于 O(n) 和 O(nk) 之间。

总结：

虽然是暴力解法，但通过优化搜索范围，可以降低平均时间复杂度。