🥴644 maximum average subarray II

https://leetcode.com/problems/maximum-average-subarray-ii/

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        
        for (int num : nums) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }
        // the average of any subarray can not be less than min of nums or greater than max of nums
        double lo = min;
        double hi = max;
        double precision = 1e-6;
        // use binary search to find the max average that satisfies the condition
        while (lo + precision < hi) {
            double mid = (lo + hi) / 2;
            if (hasAvg(nums, k, mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
    // return if there's a subarray with length greater than k and an average greater or equal to target
    private boolean hasAvg(int[] nums, int k, double target) {
        double precision = 1e-6;
        double[] tmp = new double[nums.length];
        double[] prefixes = new double[nums.length];
        // premin要设为0，因为如果window外面的大于0还不如只取window里面的
        double preMin = 0;
        double sum = 0;
        // offset by target so that we can just see if the elements sums up to greater or equal to zero
        for (int i = 0; i < nums.length; i++) {
            tmp[i] = (double)nums[i] - target;
            sum += tmp[i];
            prefixes[i] = sum;
            if (i >= k) {
                // compare it with the minimum element within the elements 
                // before the start of current k length window
                preMin = Math.min(preMin, prefixes[i - k]);
                if (prefixes[i] - preMin >= precision) {
                    return true;
                }
            }
        }
        // because we did not check the window without previous element, this is the last chance
        return prefixes[k - 1] >= precision;
    }
}

1. subarray的平均值不会超过array里的min到max的范围，据此来二分查找最大的满足条件的平均值

2. 让所有的元素都减去一个avg就只需要判断和是不是为0就知道原数组平均值是不是为avg

3. 由于subarray是大于等于k长度的，所以我们把window设置为k长度，然后记录winstart左边的prefix sum最小值，用win end处的prefix sum相减就是长度大于（没有等于）k的window的sum最大值，注意preMin初始值要设置为0，这样如果window外的min prefix大于0，我们可以直接取0得到长度等于k的window的sum值，同时这种办法检查不到没有premin的元素，要在最后返回时检查一下

4. 可以看这个视频