Problem
Given an array with positive and negative numbers, find themaximum average subarraywhich length should be greater or equal to given lengthk.
Notice
It's guaranteed that the size of the array is greater or equal to k.
Example
Given nums =[1, 12, -5, -6, 50, 3], k =3
Return15.667// (-6 + 50 + 3) / 3 = 15.667
思路一（O(n ^ 2) time, 暴力两层for循环）
思路二（O(n log n) time, Binary Search for maximum Average value）
- 因为这题没办法用O(n) 的时间内实现， 所以锁定 O(nlogn)
- 由于求的是subarray， 所以不能sort
- 于是想到binary Search + for 循环
- 首先要确定搜索的范围， 也就是先求出该数组内的max value 和 min value
- 因为没有可能存在subarray的平均值能超出这个范围的了。
- 然后取中值， 判断是否有subarray的平均值大于或等于这个中值，
- 如果有，则在【中值， max value】搜索
- 否则， 则在【min value, 中值】搜索
- 直到最后范围缩小到无限接近于零（1e-10）
public double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return 0;
}
double max = nums[0];
double min = nums[0];
for (int i = 1; i < nums.length; i++) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[i]);
}
while (max - min > 1e-10) {
double mid = min + (max - min) / 2;
if (containsMid(nums, mid, k)) {
min = mid;
} else {
max = mid;
}
}
return max;
}
private boolean containsMid (int[] nums, double mid, int k) {
int len = nums.length;
double[] preSum = new double[len + 1];
double minPre = 0;
for (int i = 1; i <= len; i++) {
preSum[i] += preSum[i - 1] + nums[i - 1] - mid;
if (i >= k && preSum[i] - minPre > 1e-10) {
return true;
} else if (i >= k) {
minPre = Math.min(minPre, preSum[i - k + 1]);
}
}
return false;
}