Maximum Average Subarray II.java

R
1521096472
tags: Array, Binary Search, PreSum

给int[] nums 和 window min size k. window size可以大于K. 找最大的连续数列average value.

- Binary Search的思想, 用在所要找的这个 average sum 上面. 大小是在[min, max]之中
- 找k的时候, 是>=k都可以, 巧用一个 min(preSum)的概念.
- 找k的时候, 画图, 可以看出来, 其实要的是 k window 里面的sum [x, i], 所以要用 sum[0, i] - sum[0, x]

需要仔细去读下面的notes.

```

/*
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 <= k <= n <= 10,000.
Elements of the given array will be in range [-10,000, 10,000].
The answer with the calculation error less than 10-5 will be accepted.

*/

/*
Thoughts:
If trying brutly, it'll be O(n^2). How about O(nLogN)?

Try binary serach on the final result: the average number, which will range from [min, max] of nums.
Should recognize that when seeing '1e-15'
http://bookshadow.com/weblog/2017/07/16/leetcode-maximum-average-subarray-ii/

Key idea:
0. start=mid, end=max.
1. Give the midAvg[min, max] as the arbitrary avg, see if we can find possible k [k ~ n], that gives average sum >= midAvg
2. If it does exist, maybe we can find larger midAvg? so set start=midAvg
3. If not exist, we should set end=midAvg

Problem:
How to effectively check we can beat given midAvg? Simply sum up k items => sum, then check sum/k >= midAvg.
Well, a bit more to it:
1. If using nums[0, k], it's easy: sum[0, k] / k will be it.
2. If using [x, i], where i - x = k. The sum will be sum[0, i] - preSum[0, x].
   Here is the core triky part: we don't have to try O(n^2) here to check all possible k in [k ~ n]
   Rather, we record preSum as the minimal value of all possible preSum as k moves.
   `sum[x, i] = sum[0 ~ i] - min(preSum's) >= 0` basically tells: for all possible k's, is there a split where preSum is smallest and makes the sum[x, i] greater than 0?
   That's the beauty to the problem: no need to calculate all possible k's: just need 1 valid solution, and we don't care which k that will be.
*/
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        double min = Integer.MAX_VALUE;
        double max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(nums[i], min);
            max = Math.max(nums[i], max);
        }
        
        double start = min;
        double end = max;
        double midAvg = max;
        while (end - start > 1e-5) {
            midAvg = start + (end - start) / 2.0;
            if (check(nums, k, midAvg)) {
                start = midAvg;
            } else {
                end = midAvg;
            }
        }
        return midAvg;
    }
    
    /**
        Return true, if there is a window with size >= k,
        such that the average sum will >= given midAvg.
     */
    private boolean check(int[] nums, int k, double midAvg) {
        double preSum = 0;
        double sum = 0;
        double minPreSum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i] - midAvg;
        }
        if (sum >= 0) {
            return true;
        }
        for (int i = k; i < nums.length; i++) {
            sum += nums[i] - midAvg;
            preSum += nums[i - k] - midAvg;
            minPreSum = Math.min(preSum, minPreSum);
            if (sum >= minPreSum) {
                return true;
            }
        }
        return false;
    }
}


```