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;
    }
}

subarray的平均值不会超过array里的min到max的范围，据此来二分查找最大的满足条件的平均值
让所有的元素都减去一个avg就只需要判断和是不是为0就知道原数组平均值是不是为avg
由于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的元素，要在最后返回时检查一下

Previous240 search a 2D matrix II Next528 random pick with weight

Last updated 2 years ago

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; } }