643. 子数组最大平均数 I Easy

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1： 输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2： 输入：nums = [5], k = 1
输出：5.00000

解题思路

输入：给定一个数组

输出：找到最大平均数，要求要是长度为k的连续子数组

本题属于固定长度滑动窗口类型问题。

我们可以使用一个滑动窗口，大小为 k，在遍历数组的过程中维护当前窗口的总和，并计算其平均值。每次窗口右移时，只需要减去左边移出元素的值，加上右边新进入元素的值，即可在 O(1) 时间内更新窗口和。

同时，用一个变量记录当前遇到的最大平均值，遍历结束后即可得到最终答案

代码实现

python

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = 0  # 初始化滑动窗口内的元素和

        # 计算第一个长度为 k 的窗口的总和
        for i in range(0, k):
            window_sum += nums[i]
        
        # 初始化最大平均值
        max_value = window_sum / k

        # 从第 k 个元素开始，滑动窗口
        for i in range(k, len(nums)):
            # 从窗口左边移除一个数（nums[i - k]），右边加入一个新数（nums[i]）
            diff = nums[i] - nums[i - k]
            window_sum += diff  # 更新窗口和

            # 计算当前窗口的平均值，并更新最大值
            max_value = max(max_value, window_sum / k)
        
        return max_value  # 返回最大平均值

javascript

const findMaxAverage = function (nums, k) {
    let windowSum = 0;

    // 先计算第一个窗口的总和（前 k 个数）
    for (let i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    // 初始最大平均值就是第一个窗口的平均值
    let maxValue = windowSum / k;

    // 滑动窗口，从第 k 个数开始往后遍历
    for (let i = k; i < nums.length; i++) {
        // 当前窗口 = 上一个窗口 + 新进元素 - 滑出元素
        const diff = nums[i] - nums[i - k];

        // 更新当前窗口的和
        windowSum += diff;

        // 更新最大平均值
        maxValue = Math.max(maxValue, windowSum / k);
    }

    // 返回最大平均值
    return maxValue;
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

链接

643 国际版

643 中文版