刷题之旅从数组类型的题目开始。第二十九道题目是子数组最大平均数 I，对应leetcode的题号为643。

image

题目描述

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

示例 1:

1
2
3
输入: [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个地算结果，最终比较出最大的结果即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        //max中存储结果
        double max = -Double.MAX_VALUE;
        for(int i=0;i<nums.length;i++){
            int temp = 0;
            if(i+k<=nums.length){
                for(int j=i;j<i+k;j++){
                    temp += nums[j];
                }
                if((double)temp/k > max){
                    max = (double)temp/k;
                }
            }
        }
        return max;
    }
}

执行的结果为：

1
2
执行用时 :430 ms, 在所有 Java 提交中击败了21.91%的用户
内存消耗 :41.8 MB, 在所有 Java 提交中击败了22.89%的用户

不过能不能优化下呢？很显然在循环中对于temp的求解发生了重复，其实更新的只是一头一尾的数据，中间还是一样的，那么借用滑动窗口的思想进行优化下。

提交代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        //先算出第一组的平均数
        int sum = 0;
        for(int i=0;i<k;i++){
            sum += nums[i];
        }
        double max = (double)sum/k;
        for(int i=k;i<nums.length;i++){
            //计算窗口内的值，即i-k+1到i之间的数字，一直往后滑动
            sum -= nums[i-k];
            sum += nums[i];
            double res = (double)sum/k;
            if(res > max){
                max = res;
            }
        }
        return max;
    }
}

效果得到了明显的提升，执行的结果为：

1
2
执行用时 :7 ms, 在所有 Java 提交中击败了43.33%的用户
内存消耗 :40.7 MB， 在所有 Java 提交中击败了76.93%的用户