Leetcode-643-子数组最大平均数1

Leetcode-643-子数组最大平均数 I

题目描述

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例：

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

提示：

1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。

方法一 ： 滑动窗口

• 由于规定了子数组的长度为 k，因此可以通过寻找子数组的最大元素和的方式寻找子数组的最大平均数，元素和最大的子数组对应的平均数也是最大的。

假设两个不同的子数组的长度都是 k，这两个子数组的元素和分别是 x 和 y，
则这两个子数组的平均数分别是 x/k 和 y/k。
如果 x≥y，则有 x/k ≥ y/k，即如果一个子数组的元素和更大，则该子数组的平均数也更大。

• 为了找到子数组的最大元素和，需要对数组中的每个长度为k的子数组为别计算元素和。对于长度为n的数组，当k <= n的时候，有n - k + 1个长度为k的子数组
• 如果直接计算每个子数组的元素和，则时间复杂度过高，无法通过全部测试用例，因此需要使用时间复杂度更低的方法计算每个子数组的元素和。

---

滑动窗口推导

• 上述过程可以看成维护一个长度为k的滑动窗口。当滑动窗口的下标范围从[i - k,i - 1] 到 [i - k + 1,i]时，nums[i - k] 从窗口移除，nums[i] 进入到窗口内

• 利用上述关系，可以在O(1) 的时候内通过sum_i-1 得到 sum_i

• 

• 在上述过程中维护最大的子数组元素和，记为maxSum，子数组的最大平均数即为 maxSum/k。

• 需要注意返回值是浮点型，因此计算除法时需要进行数据类型转换。

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        // 1. 长度小于k的时候，直接初始化sum
        int sum = 0;
        int n = nums.length;
        for(int i = 0;i < k;i++){
            sum += nums[i];
        }

        // 2. 长度大于等于k的时候，比较最大的连续子数组和
        int maxSum = sum;
        for(int i = k;i < n;i++){
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum,sum);
        }
        
        // 3. 返回浮点结果
        return 1.0 * maxSum/k;
    }
}

复杂度分析：

• 时间复杂度 : O(n)
• 空间复杂度 ：O(1)

打赏