描述
给出一个整数数组，有正有负。找到这样一个子数组，他的长度大于等于 k，且平均值最大。
注意事项
保证数组的大小 >= k
样例
给出 nums = [1, 12, -5, -6, 50, 3], k = 3
返回 15.667 // (-6 + 50 + 3) / 3 = 15.667
代码
public class Solution {
/**
* @param nums an array with positive and negative numbers
* @param k an integer
* @return the maximum average
*/
public double maxAverage(int[] nums, int k) {
double l = Integer.MAX_VALUE, r = Integer.MIN_VALUE;
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;
}
// 函数用于判断数组中是否存在大于等于k个相邻数，每个数减去mid的总和大于0
// i 在变化题目中虽然没定义j，但每次的min_pre都是j在变化，要确保i - j >= k
private boolean check_valid(int nums[], double mid, int k) {
int n = nums.length;
// min_pre用于记录最小的一个sum[j]
double min_pre = 0;
// 数组定义n + 1，sum[0] ~ sum[n],sum[n] 对应 nums[n -1]
double[] sum = new double[n + 1];
sum[0] = 0;
for (int i = 1; i <= n; ++i) {
sum[i] = sum[i - 1] + nums[i - 1] - mid;
if (i >= k && sum[i] - min_pre >= 0) {
return true;
}
if (i >= k)
/* 此处需要注意的是i - k + 1这个取值即i - (k - 1)
* 保证当前情况下i 和 j 之间相差k - 1个数，for循环下一轮
* i++,这时i 和 j之间就差了k个数，保证了子数组长度大于等于k
*/
min_pre = Math.min(min_pre, sum[i - k + 1]);
}
return false;
}
}
思路：
这题本身不太容易理解
- 可以枚举所有的长度大于等于k的子数组计算平均值，并对所有得到的平均值求最大值，这样可以做到时间复杂度O(n^2)，但是会超时。
或许有同学会想到是不是可以只看长度为k的子数组，因为如果没有长度限制，那么显然最大平均值子数组就是数组中最大的数（长度为1的子数组）， 而且刚好样例给出的数据是满足长度为k的所有子数组的最大平均值随着k增大而减小的。很可惜这个想法是错误的，很容易举出反例，对于[1, -1, 1]， 长度1子数组的最大平均值为1，长度2的为0，长度3的为1/3，如果题目给出k=2，则应输出返回1/3而非0。 - 有些最值问题可以转化为判断问题从而用二分法求得答案。对于n个数a(0),a(1),……,a(n-1)，以及一个数A，如果存在一个子数组起始于i，长为L>=k，使得其平均值大于等于A，即(a(i)+a(i+1)+……+a(i+L-1))/L >= A，那么我们所求的答案应当大于等于A；反之如果对于所有长度大于等于k的子数组，其平均值均小于A，那么我们所求的答案也必然小于A。
- 如何判断是否存在长度至少为k的子数组，其平均值大于等于A？
a. 观察式子(a(i)+a(i+1)+……+a(i+L-1))/L >= A，其等价于(a(i)-A)+(a(i+1)-A)+……+(a(i+L-1)-A)>=0，令b(0)=a(0)-A , b(1)=a(1)-A , …… , b(n-1)=a(n-1)-A，那么判断a数组中是否存在长度至少为k的子数组平均值大于等于A，就变成了判断b数组中是否存在长度至少为k的子数组和大于等于0， 只要求出b数组长度至少为k的子数组的最大和与0比较即可。
b. 求长度大于等于k的最大和子数组比原问题容易的多，令s为b的前缀和子数组，即s(i)=b(0)+b(1)+……+b(i-1)，且s(0)=0，那么b(j)到b(i-1)的区间和可表示为s(i)-s(j)，找长度大于等于k的最大和子数组等价于找i,j，满足i-j>=k，且使s(i)-s(j)最大。固定i，则要使s(i)-s(j)最大，s(j)应最小，同时也应满足j<=i-k，令p(i) = min{s(j)}， j<=i-k，故 i 固定时s(i)-s(j)的最大值为s(i)-p(i)，枚举所有i即可得到最终的最大值。因为s(i),p(i)均可通过递推得到，故时间复杂度为O(n)。
c. 这样一来，我们就可以二分答案，二分的初始区间可以设置为[min{a(i)},i=0~n-1 , max{a(i)},i=0~n-1]，因为一组数的平均值不会小于这组数的最小值，也不会大于这组数的最大值。
注：
- 对于二分值A，通过前面讲的方法以O(n)的时间判断是否有子数组的平均值大于等于A，若有则答案大于等于A，若没有，则答案小于A。
- 二分至区间长度小于所需精度，即可返回该值。时间复杂度为O(n*log((MAX-MIN) / eps))，其中MIN、MAX分别为a数组的最小值和最大值，eps为要求的精度。
另一种形式的写法更有助于理解上面代码的变量作用：
640.jpeg
