Given an array with positive and negative numbers, find the maximum average subarray which length should be greater or equal to given length k.
思路：
对平均值进行二分。一个数组平均的最大不会超过数组最大值，也不会低于数组最小值。也就是说，这个平均值肯定在数组最大值和最小值的范围区间内。
用前缀和数组判断是否数组中是否有一段长度大于等于k的子数组，平均数大于等于mid。如果存在，就把left=mid，如果不存在就把right=mid。这样不断所有l和r的距离，直到重合。left 就是所能找到的最大平均值。
复杂度：
时间： O(nlog(max_val−min_val))O(nlog(max_val−min_val))
空间：O(n)
public double maxAverage(int[] nums, int k) {
double result = 0.0;
if(nums == null || nums.length < k) {
return result;
}
double l = Integer.MAX_VALUE;
double r = Integer.MIN_VALUE;
//find the largest number and smallest number in the array
for(int i = 0; i < nums.length; i++){
if(nums[i] < l) {
l = nums[i];
}
if(nums[i] > r){
r = nums[i];
}
}
while(r - l >= 1e-6){
double mid = (l + r) / 2.0;
if(check_valid(nums, mid, k)){
l = mid;
}else{
r = mid;
}
}
return l;
}
private boolean check_valid(int nums[], double average, int k) {
int n = nums.length;
double min_pre = 0;
double[] sum = new double[n + 1];
sum[0] = 0;
for (int i = 1; i <= n; ++i) {
// 原数组中的每一个数减去这个mid
sum[i] = sum[i - 1] + nums[i - 1] - average;
if (i >= k && sum[i] - min_pre >= 0) {
return true;
}
if (i >= k)
min_pre = Math.min(min_pre, sum[i - k + 1]);
}
return false;
}
网友评论