刷题之旅从数组类型的题目开始。第二十九道题目是子数组最大平均数 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%的用户