## 题目描述：

LeetCode 644. Maximum Average Subarray II

Given an array consisting of `n` integers, find the contiguous subarray whose length is greater than or equal to `k` that has the maximum average value. And you need to output the maximum average value.

Example 1:

```Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation:
when length is 5, maximum average value is 10.8,
when length is 6, maximum average value is 9.16667.
Thus return 12.75.
```

Note:

1. 1 <= `k` <= `n` <= 10,000.
2. Elements of the given array will be in range [-10,000, 10,000].
3. The answer with the calculation error less than 10-5 will be accepted.

## 解题思路：

```初始令lo = min(nums)，hi = max(nums)

令lastMid = mid，mid = (lo + hi) / 2

若一趟遍历检查发现nums中存在长度不小于k的连续子数组，并且均值>= mid：令lo = mid

否则：令hi = mid

## Java代码：

``````public class Solution {
public double findMaxAverage(int[] nums, int k) {
double lo = Double.POSITIVE_INFINITY;
double hi = Double.NEGATIVE_INFINITY;
for (int num : nums) {
lo = Math.min(lo, num);
hi = Math.max(hi, num);
}
double mid = hi, lastMid = lo;
while (Math.abs(mid - lastMid) > 1e-5) {
lastMid = mid;
mid = (lo + hi) / 2.0;
if (check(nums, k, mid)) {
lo = mid;
} else {
hi = mid;
}
}
return mid;
}

public boolean check(int[] nums, int k, double mid) {
double minVal = Double.POSITIVE_INFINITY;
double sums = 0, sumt = 0;
for (int i = 0; i < nums.length; i++) {
sums += nums[i] - mid;
if (i >= k - 1 && sums >= 0) {
return true;
}
if (i >= k) {
sumt += nums[i - k] - mid;
minVal = Math.min(minVal, sumt);
if (sums >= minVal) {
return true;
}
}
}
return false;
}

}
``````

Pingbacks已关闭。