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 tok.

Have you met this question in a real interview?

Yes

Example

Given nums =[1, 12, -5, -6, 50, 3], k =3

Return15.667// (-6 + 50 + 3) / 3 = 15.667

平均值会在最大和最小值之间

二分枚举答案，并且通过O(n）时间来判断是否至少有一个长度大于k的子数组可以达到这个平均值，

如果有，那么提高起点
如果没有，那么减少中点

在判断是否存在一个大于k的子数组有大于mid的平均值时，可以把它转化为一个sum的问题，左右两边都减去mid

(2 + 3 + 5) / 3 > mid => 2 + 3 + 5 > mid * 3 => 2 + 3 + 5 - mid * 3 > 0

所以只需要将左侧所有数值减去mid在求前缀和，并且保留遍历过的最小的前缀和，计算当前前缀和和之前最小前缀和的差，就是当前最大前缀和，如果这之间有k个数并且当前最大前缀和大于0，则代表至少有一个大于k的区间会有平均值大于mid

还要注意题目要求要精确到多少位
p.s. 如果需要精确到3位，则一定要保留3 + 2 位才可以保证精确到 3位， 1e - 6来表示

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) {
        // write your code here
        if (k == 0) {
            return 0.0;
        }

        double start = Integer.MIN_VALUE, end = Integer.MAX_VALUE;


        while (end - start >= 1e-6) {
            double mid = start + (end - start) / 2.0;
            if (hasMid(nums, k, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return end;
    }

    public boolean hasMid(int[] nums, int k, double mid) {
        double[] sum = new double[nums.length + 1];
        sum[0] = 0;
        double pre_min = 0.0;

        for (int i = 1; i <= nums.length; i++) {
            sum[i] = sum[i - 1] + nums[i - 1] - mid;

            //sum[i] - pre_min is the sum from i - 1 to pre_min 
            if (i >= k && sum[i] - pre_min >= 0) {
                return true;
            }

            //if there is at least k elements, then we can remove from the beginning
            //by keep the min of the starting item and pre_min
            if (i >= k) {
                pre_min = Math.min(pre_min, sum[i - k + 1]);
            }
        }

        return false;

    }
}