解题利器：滑动窗口算法详解与应用示例【滑动窗口】

在解决算法问题时，有时我们会面对需要求解 固定大小 的 连续 子数组的和或平均数的情况。这类问题通常可以通过滑动窗口算法高效解决。

滑动窗口算法详解

滑动窗口算法是一种在数组或字符串上求解子数组或子串问题的有效技术。它通过维护一个窗口（通常是一个子数组或子串），在这个窗口上滑动并在每个位置计算所需的结果。这种方法常常可以将暴力解法的时间复杂度从 $O(n^2)$ 降低到 $O(n)$，大大提高了算法的效率。

解决思路

1. 初始化阶段

首先，我们需要初始化一个窗口来计算初始状态下的和或其他需求。例如，在求解长度为 k 的连续子数组的最大平均数时，我们可以先计算前 k 个元素的和作为初始窗口的状态。

// 初始化前 k 个元素的和
double current_sum = 0;
for (int i = 0; i < k; ++i) {
    current_sum += nums[i];
}
double max_sum = current_sum;

2. 滑动窗口过程

接下来，从索引 k 开始遍历数组，每次移动窗口时，更新窗口的状态。具体操作是减去窗口左边界的元素，并加上窗口右边界的元素。这一步骤可以通过简单的加减操作实现，避免了重复计算整个窗口的开销。

for (int i = k; i < nums.size(); ++i) {
    current_sum += nums[i] - nums[i - k]; // 更新窗口的和
    max_sum = max(max_sum, current_sum);  // 更新最大和
}

3. 计算最终结果

最后，通过已经得到的最大和除以 k，即可得到最大平均数。这一步是问题的最终求解步骤。

double max_average = max_sum / k;

应用示例

现在，我们通过一个具体的示例来说明滑动窗口算法的应用。

643. 子数组最大平均数 I - 力扣（LeetCode）

问题描述

给定一个整数数组 nums 和一个整数 k，求长度为 k 的连续子数组的最大平均数。

示例

假设 nums = [1, 12, -5, -6, 50, 3]，k = 4。

1. 初始化阶段：

   • 计算前 k 个元素的和：current_sum = 1 + 12 - 5 - 6 = 2。
   • 设置 max_sum = current_sum。

2. 滑动窗口过程：

   • 从索引 k = 4 开始，依次计算并更新窗口的和。
   • 在每次更新窗口时，比较并更新 max_sum。

3. 计算最终结果：

   • 最大平均数为 max_average = max_sum / k = 12.75。

解决这道题的关键是要找到长度为 k 的连续子数组，使得这个子数组的平均数最大。双层循环的暴力解法会导致时间复杂度过高，无法通过所有测试用例。我们需要使用更高效的方法来解决这个问题。

步骤

1. 初始化窗口和：计算数组前 k 个元素的和，作为初始窗口的和。
2. 滑动窗口：从 k 开始，逐步向右滑动窗口。在每一步中，将窗口的右边界元素加入当前窗口和，将窗口的左边界元素移出当前窗口和。
3. 更新最大和：在每一步中，更新当前窗口和，并记录最大和。
4. 计算最大平均数：使用最大和除以 k，得到最大平均数。

具体实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);

        // Step 1: Initialize the sum of the first window
        double current_sum = 0;
        for (int i = 0; i < k; ++i) {
            current_sum += nums[i];
        }
        double max_sum = current_sum;

        // Step 2: Slide the window across the array
        for (int i = k; i < nums.size(); ++i) {
            current_sum += nums[i] - nums[i - k]; // Update the window sum
            max_sum = max(max_sum, current_sum);  // Update the max sum if current sum is greater
        }

        // Step 3: Return the maximum average
        return max_sum / k;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 12, -5, -6, 50, 3};
    int k = 4;
    double result = sol.findMaxAverage(nums, k);
    cout << "The maximum average of a subarray of length " << k << " is: " << result << endl;
    return 0;
}

详细解释

1. 初始化：

   • current_sum 初始化为前 k 个元素的和。
   • max_sum 初始化为 current_sum。

2. 滑动窗口：

   • 从索引 k 开始，遍历数组。
   • 每次更新 current_sum 时，减去窗口左边界的元素，加上窗口右边界的元素。
   • 使用 max 函数更新 max_sum，确保记录的总是最大的窗口和。

3. 返回结果：

   • 将 max_sum 除以 k，得到最大平均数，并返回结果。

优化技巧

在代码中使用以下优化技巧可以提高运行速度：

ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

这几行代码可以加快输入输出速度，适合在需要频繁进行输入输出操作的竞赛环境中使用。

总结

通过以上的步骤，我们成功地使用滑动窗口算法解决了求解最大平均数的子数组问题。滑动窗口算法在处理子数组或子串问题时具有明显的优势，能够有效提高算法的执行效率，是解决类似问题时值得掌握和应用的一种重要技巧。

原文地址：https://blog.csdn.net/qq_22841387/article/details/140732028

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！