LeetCode] 644.Maximum Average Subarray II

LeetCode 644. Maximum Average Subarray II

lintcode 671

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.

题目大意：

给定包含n个整数的数组，寻找长度大于等于k的连续子数组的平均值的最大值。

没有买leetcode，所以复制粘贴了题目，这道题看起来跟他的兄弟差不多，但是实际上差很多。。。lintcode 671 这个一模一样的就是hint和限制条件没有。所以可以用这个来测。

这个解释的很详细 https://leetcode.com/articles/maximum-average-subarray-ii/

这个也很好 http://blog.csdn.net/zjucor/article/details/75199933

我开始用的是暴力解法，就是把它兄弟重复很多遍，当然，超时哦。然后就不知道怎么办了，看的答案，看完恍然大悟，原来里面有套路：

1. 只要满足一定误差，所以用二分，直接二分最后的平均值

2. 在判断某个平均值是否满足时，转换为求连续子数组的和大于0（这个求平均值的套路可以记一下）

城市套路深啊！这个在leetcode原题目里有个精确度，所以给了很大提示。
1. 找出最大最小值；
2. 误差没达到就一直二分；
3. 二分条件： 如果在循环找符合条件的mid的时候，只要一条符合就返回true，所有都不符合，说明mid设置太大了，真正的均值，在mid左侧。
4. 开始以为check函数要存在一个数组里，把算出来的num[i]-mid，后来发现我们就不用maintain这个数组，在循环里，保持一个pre的指针一直里sum，k个远，然后pre指针的数是pre之前所有求和数的最小值就行，min_sum = Math.min(prev, min_sum)。就这一句简单的话，就把>k这个给破了，高！

AC Solution:

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) {
        // Binary search. Set a mid, find if one part of nums sum up larger than mid, if yes, min = mid; if none of sum larger than mid, max = mid
        // Avg value must be in the middle of min and max.
        double max = Integer.MIN_VALUE;
        double min = Integer.MAX_VALUE;
        for(int i:nums){
            max = Math.max(max, i);
            min = Math.min(min, i);
        }
        double error = max - min;
        while(error > 0.00001){
            double mid = min + (max - min)/2;
            if(checkExist(nums, k, mid)){
                min = mid;
            }else{
                max = mid;
            } 
            error = Math.abs(max - min);
        }
        return min;
    }
    
    public boolean checkExist(int[] nums, int k, double mid){
        double sum = 0, prev = 0, min_sum = 0;
        for (int i = 0; i < k; i++)
            sum += nums[i] - mid;
        if (sum >= 0)
            return true;
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - mid;
            prev += nums[i - k] - mid;
            min_sum = Math.min(prev, min_sum);
            if (sum >= min_sum)
                return true;
        }
        return false;
    }
}