Maximumu Average Subarray I

643. 子数组最大平均数I

分析

用一个变量 sum 表示当前窗口中 k 个数的和
遍历数组，依次更新 sum，当窗口大小达到 k 时，计算当前窗口的平均值，并尝试更新最大平均值
如果窗口大小超过 k，将窗口的左端值从 sum 中减去，同时将窗口右端的新值加上
遍历结束后，返回最大平均值

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution
{
public:
    double findMaxAverage(vector<int>& nums, int k)
    {
      double max_average = INT_MIN; // 用于存储最大平均数
      double sum = 0; // 当前窗口的总和
      for (int i = 0, j = 0; i < nums.size(); i++) // 遍历数组
      {
        sum += nums[i]; // 将当前元素加入窗口
        if (i - j + 1 > k) // 如果窗口大小超过 k
          sum -= nums[j++]; // 移除窗口左端的值
        if (i >= k - 1) // 确保窗口大小恰好为 k 时
          max_average = std::max(max_average, sum / (double)k); // 计算平均值并更新最大值
      }
      return max_average; // 返回最大平均值
    }
};