今天遇到了一道题，本来题的不难的，但是就是因为加入了很多的限制，导致了这个题比较棘手。
题意
给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且
平均值最大。
样例
给出 nums = [1, 12, -5, -6, 50, 3], k = 3
返回 15.667 // (-6 + 50 + 3) / 3 = 15.667
注意事项
保证数组的大小 >= k
1.传统的方法(超时)
这个题的传统非常的容易，这里不便再赘述
public static double maxAverage(int[] nums, int k) {
//记录当前k(或者大于k)位数字和
double sum = 0;
double max = Integer.MIN_VALUE;
if(nums == null || nums.length == 0 || k == 0){
return 0;
}
for(int j = k; j <= nums.length; j++){
//初始化为0
sum = 0;
for(int i = 0; i < nums.length; i++){
if(i >= j){//当i > j时，计算最大值
max = ((sum * 1.0 / j) > max) ? sum * 1.0 / j : max;
sum -= nums[i - j]; //需要减去当前选择的数字的第一个，因为即将在加入一个
}
//加入一个数字
sum += nums[i];
}
max = ((sum * 1.0 / j) > max) ? sum * 1.0 / j : max;
}
return max;
}
2.二分法
对的，又是二分法。跟前面的快慢指针一样，这里也是非常规的二分法使用。
(1).题意介绍
这个题让我们求的是一个数组的子数组(长度大于等于k)的最大平均值,记住不是最大值，是最大平均值。因为得出最大值不一定能够推出最大的平均值，因为平均值不仅受和的影响，还要受个数影响。
(2).算法概述
首先一个数组的和的平均值一定在这个数组中的最小值和最大值之间。这一点肯定没有争议。
其次，我们现在要做的就是--二分，在这个范围里面，不断的二分，直到找到我们想要的值，但是又应该怎么二分呢？
我们可以这样来假设，假设 最大值为max,最小值为min，中间值为 mid = (min + max ) /2.0(这里为什么要除以2.0，而不是2呢？那是我们在[min, max]区间求得我们想要的那个平均值，而这个平均值不可能总是整数，有可能是小数(double)，所以，我们除以2.0而不是2)。假设nums数组(nums[0], nums[1], nums[2], nums[3].......)，如果存在两个下标i,j(i > j),长度i - j >= k,使其(相当于是nums数组的子数组)平均值大于等于mid的值，那么：
(nums[i] + nums[i + 1] + ...... + nums[j]) / (i - j) >= mid.
所以，得出我们想要的答案必定在[mid, max]区间里面；反之，如果不存在这两个下标，也就是所有的子数组的平均值都小于mid，那么我们求得最终的答案肯定小于mid,所以最终的答案肯定在[min, mid]。
那么，怎么判断一个子数组(长度L >= k)和的平均值大于mid呢？
这个是我们这个问题的一个难点，我们用数学公式来表达,如图所示：
如图上的结论，我们还可以假设s数组，其中
s[0] = 0;
s[1] = b[0];
s[2] = b[0] + b[1] = s[1] + b[1];
s[3] = b[0] + b[1] + b[2] = s[2] + b[2];
那么b[j]到b[i](i > j)区间和为s[i + 1] - s[j]。要想找出区间和(长度大于等于k)的最大值，等价于找i,j，满足i - j >= k并且使得s[i] - s[j]最大。要想求出s[i + 1] - s[j]的最大值，我们固定i,只要s[j]最小的话，那么s[i + 1] - s[j]就最大了。
(3).代码
public static double maxAverage(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return 0;
}
double max = Integer.MIN_VALUE;
double min = Integer.MAX_VALUE;
for(int i = 0; i < nums.length; i++){
if(nums[i] > max){
max = nums[i];
}
if(nums[i] < min){
min = nums[i];
}
}
while (max - min >= 1e-6) {
double mid = (max + min) / 2.0;
if(binarySearch(nums, mid, k)){//表示最大的平均值在[min, mid]里面
min = mid;
}else{//表示最大的平均值在[mid, max]里面
max = mid;
}
}
return min;
}
private static boolean binarySearch(int[] nums, double mid, int k) {
//用来记录区间和的
double sum[] = new double[nums.length + 1];
double min = 0;
sum[0] = 0;
for (int i = 1; i <= nums.length; i++) {
//计算每个点的区间和
sum[i] = sum[i - 1] + (nums[i - 1] - mid);
//min相当于是s[j]，不过这里是一步一步的取小值得出来的
if (i >= k && sum[i] >= min) {//表示有b数组的和>=0，则取值范围变为[mid, max]
return true;
} if (i >= k) {
min = Math.min(min, sum[i - k + 1]); //一步一步的取小值
}
}
return false;
}
