子数组最大平均数 II

/*
 * Leetcode题目: 子数组最大平均数 II
 * 题目描述: 给定一个包含 n 个整数的数组，找出平均值最大且长度至少为 k 的连续子数组，并输出该最大平均值。
 * 题目思路:
 * 1. 使用二分查找法来解决该问题。
 * 2. 首先确定最大平均值的上下界：最大值设为数组的最大值，最小值设为数组的最小值。
 * 3. 使用二分法不断缩小平均值的范围，并在每一步验证当前平均值是否可行。
 * 4. 验证方法为：遍历数组计算前缀和，并判断是否存在长度至少为 k 的子数组，其平均值大于当前的候选平均值。
 */
import java.util.stream.*;
public class MaxAverageSubarrayStream {
    public double findMaxAverage(int[] nums, int k) {
        double left = IntStream.of(nums).min().orElse(Integer.MIN_VALUE);
        double right = IntStream.of(nums).max().orElse(Integer.MAX_VALUE);
        while (right - left > 1e-5) {
            double mid = left + (right - left) / 2;
            if (canFindLargerAverage(nums, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }
 
    private boolean canFindLargerAverage(int[] nums, int k, double mid) {
        double sum = 0, prev = 0, minSum = 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;
            minSum = Math.min(minSum, prev);
            if (sum >= minSum) return true;
        }
        return false;
    }
}