643.子数组最大平均数

(Updated: )
LeetCode
,

Q

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

示例 1:

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

A

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

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int rs = -Integer.MAX_VALUE;
        for(int i = 0;i<=nums.length-k;i++){
            int sum = 0;
            for(int j = 0;j<k;j++){
                sum+=nums[i+j];
            }
            rs = (sum >= rs) ? sum:rs;
        }
        double rs2 = rs;
        return rs2/k;
    }
}

暴力

  • 思路
    遍历数组，逐个找出最大子数组并比较最大值。
    由于int类型计算速度比double快，在比较数组时使用int类型，计算平均值时使用double类型。

  • 时间复杂度
    O(N*K)，其中 N 是数组的长度,K为输入的子数组长度。

  • 空间复杂度
    O(1)

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int sum = 0;
        int n = nums.length;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        int maxSum = sum;
        for (int i = k; i < n; i++) {
            sum = sum - nums[i - k] + nums[i];
            maxSum = Math.max(maxSum, sum);
        }
        return 1.0 * maxSum / k;
    }
}


  • 思路
    用 $sum_i$ 表示数组 $nums$ 以下标 $i$ 结尾的长度为 $k$ 的子数组的元素和，其中 $i≥k−1$，则 $sum_i$ 的计算方法如下：
    $$sum_{i} = \sum_{j=i-k+1}^inums_{j}$$
    当 $i>k−1$ 时，将上式的 $i$ 替换成 $i−1$，可以得到以下算式：
    $$sum_{i-1} = \sum_{j=i-k}^{i-1}nums_{j}$$
    将上述两个算式相减，可以得到如下关系：
    $$sum_{i}-sum_{i-1} = nums[i]-nums[{i-k}]$$
    整理得到：
    $$sum_{i}=sum_{i-1}+nums[i]-nums[{i-k}]$$
    上述过程可以看成维护一个长度为 $k$ 的滑动窗口。当滑动窗口从下标范围 $[i-k,i-1]$ 移动到下标范围 $[i−k+1,i]$ 时，${nums}[i-k]$ 从窗口中移出，$nums[i]$ 进入到窗口内。
    即某长度为K的子数组向后移动时，将子数组第一位移除窗口，使子数组结尾一位的下一位进入窗口。
    ​第一个子数组的元素和 $sum_{k-1}$ 需要通过计算 $nums$ 的前$k$个元素之和得到，从$sum_k$到$sum_{n-1}$的值则可利用上述关系快速计算得到。只需要遍历数组 $nums$ 一次即可得到每个长度为 $k$ 的子数组的元素和，时间复杂度是 $O(n)$

  • 时间复杂度
    O(N)

  • 空间复杂度
    O(1)