LeetCode 644. 子数组最大平均数 II

2023-04-13 HGNULB 约 10 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 644. 子数组最大平均数 II

题意分析

要什么：找出长度不小于 k 的连续子数组，使其平均值最大，返回这个最大平均值，误差容限 $10^{-5}$。
约束透露的信号：与「长度恰为 k」的版本相比，长度变成了一个下界，候选区间数量从 $O(n)$ 膨胀到 $O(n^2)$，定长窗口的增量维护彻底失效——因为右端点固定时左端点不再唯一。题目还明确给出误差容限而不是要求精确值，这几乎是在提示：答案是一个实数，可以二分逼近而不必解析求出。元素范围有限（绝对值不超过 $10^4$），意味着答案必然落在 [min(nums), max(nums)] 这个已知区间里，二分有天然边界。
边界：k 不超过 n，一定存在合法解；元素可为负，答案也可能为负，区间下界必须取数组最小值而非 0；长度「至少 k」包含 k 本身，判定时不能写成严格大于；由于是实数二分，终止条件只能靠精度或固定迭代次数，不能靠 left < right。

解法：二分平均值 + 前缀和可行性检查

核心思路

暴力是枚举所有左右端点、用前缀和 $O(1)$ 求区间和再除以长度，时间 $O(n^2)$，$n$ 到 $10^4$ 以上就吃紧。
瓶颈在于「平均值」这个量对区间的依赖是分式的（和除以长度），既不可加也不单调，无法像求最大子数组和那样一遍扫过去。
突破点是把「求最值」翻转成「判定」：与其直接算最大平均值 $A$，不如问「是否存在长度至少为 k 的子数组，平均值 $\ge x$」。记这个判定为 $P(x)$，显然 $x$ 越小越容易满足，所以 $P$ 关于 $x$ 单调——这正是二分成立的前提，而原问题的答案恰好是使 $P(x)$ 为真的最大 $x$。
判定还能进一步化简：区间 [l, r] 的平均值 $\ge x$ 等价于 $\sum_{i=l}^{r} nums[i] \ge x \cdot (r - l + 1)$，把右边挪过去就是 $\sum_{i=l}^{r} (nums[i] - x) \ge 0$。于是「平均值」被消掉，问题变成：把每个元素减去 x 得到新数组 b，判断 b 里是否存在长度至少为 k 的子数组，其和非负。这一步是全题的关键，它把分式约束线性化了。
对新数组做前缀和 pre，区间 [l, r] 的和等于 pre[r+1] - pre[l]，于是判定变成：是否存在 i - j >= k 且 pre[i] - pre[j] >= 0。固定右端 i，只需知道 pre[0..i-k] 中的最小值。由此得到判定过程的不变量：扫描到 i 时，minPre 恰好等于 pre[0..i-k] 的最小值，一边推进 i 一边把新解禁的 pre[i-k] 并入 minPre，整个判定就是 $O(n)$。

解题步骤

把二分区间初始化为 left = min(nums)、right = max(nums)。为什么这样取：任何子数组的平均值都不小于数组最小元素、不大于最大元素，答案必在此闭区间内；取 0 或固定常数当边界在元素全负或全大时会漏掉答案。

固定迭代 60 次，每轮取 mid = (left + right) / 2。为什么用固定次数而不是 while (right - left > eps)：初始区间宽度不超过 $2 \times 10^4$，每次折半，60 次后残余宽度约 $2 \times 10^4 / 2^{60}$，远小于要求的 $10^{-5}$，既保证精度又杜绝浮点比较导致的死循环；相对误差型的 eps 判据在数值接近 0 时容易永远不满足。

判定为真时令 left = mid，为假时令 right = mid。为什么真值时收左边界：我们要的是「使判定成立的最大 x」，成立说明答案不小于 mid，可行域在右半边；不成立说明答案严格小于 mid，可行域在左半边。注意这里不能写 left = mid + 1 之类的整数二分习惯，实数没有相邻的概念。

判定函数里先构造 pre[i] = pre[i-1] + (nums[i-1] - mid)。为什么减 mid 要放进前缀和而不是事后补：只有减完之后区间和的符号才直接对应平均值与 mid 的大小关系，否则还要带着长度做乘法，等于没做化简。

判定函数里让 i 从 k 走到 n，每轮先用 pre[i-k] 更新 minPre，再检查 pre[i] - minPre >= 0。为什么先更新再检查：minPre 必须覆盖所有满足 i - j >= k 的 j，而 j = i - k 正是本轮新变得合法的那个下标；顺序反了会漏掉恰好长度为 k 的区间。为什么 minPre 初值是 0：pre[0] = 0 是合法的左端点（对应从下标 0 开始的子数组），必须参与取最小。

返回 left。为什么返回 left 而不是 right：left 始终是「已被验证可行」的那一侧，right 是「已被验证不可行」的一侧；二分结束时两者相差远小于容限，但返回可行侧在语义上更严谨。

以 nums = [1, 12, -5, -6, 50, 3]、k = 4 走一遍（答案 12.75）。初始 left = -6、right = 50。第一轮 mid = 22：新数组 nums - 22 为 [-21, -10, -27, -28, 28, -19]，前缀和 pre = [0, -21, -31, -58, -86, -58, -77]。i = 4 时 minPre = min(0, pre[0]) = 0，pre[4] - 0 = -86 < 0；i = 5 时 minPre = min(0, pre[1]) = -21，pre[5] + 21 = -37 < 0；i = 6 时 minPre = min(-21, pre[2]) = -31，pre[6] + 31 = -46 < 0。判定为假，right = 22。第二轮 mid = 8：新数组为 [-7, 4, -13, -14, 42, -5]，前缀和 pre = [0, -7, -3, -16, -30, 12, 7]。i = 4 时 minPre = 0，-30 < 0；i = 5 时 minPre = min(0, pre[1]) = -7，pre[5] + 7 = 19 \ge 0，判定为真并立即返回——它对应的区间是 pre[5] - pre[1]，即下标 1 到 4 的子数组 [12, -5, -6, 50]，长度 4 满足下界，平均值 12.75 确实不小于 8。于是 left = 8。此后区间在 [8, 22] 内继续折半，逐步向 12.75 收敛，60 轮后 left 与真值的差远小于 $10^{-5}$。

代码实现

// 核心实现：二分平均值 + 前缀和可行性检查，维护必要状态并避免重复处理。
class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double left = nums[0];
        double right = nums[0];
        for (int x : nums) {
            left = Math.min(left, x);
            right = Math.max(right, x);
        }

        for (int t = 0; t < 60; t++) {
            double mid = (left + right) / 2;
            if (check644(nums, k, mid)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return left;
    }

    private boolean check644(int[] nums, int k, double mid) {
        int n = nums.length;
        double[] pre = new double[n + 1];
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + (nums[i - 1] - mid);
        }

        double minPre = 0.0;
        for (int i = k; i <= n; i++) {
            minPre = Math.min(minPre, pre[i - k]);
            if (pre[i] - minPre >= 0) {
                return true;
            }
        }
        return false;
    }
}

// 核心实现：二分平均值 + 前缀和可行性检查，维护必要状态并避免重复处理。
func findMaxAverage(nums []int, k int) float64 {
    left, right := float64(nums[0]), float64(nums[0])
    for _, x := range nums {
        if float64(x) < left {
            left = float64(x)
        }
        if float64(x) > right {
            right = float64(x)
        }
    }

    for t := 0; t < 60; t++ {
        mid := (left + right) / 2
        if check644(nums, k, mid) {
            left = mid
        } else {
            right = mid
        }
    }
    return left
}

func check644(nums []int, k int, mid float64) bool {
    n := len(nums)
    pre := make([]float64, n+1)
    for i := 1; i <= n; i++ {
        pre[i] = pre[i-1] + float64(nums[i-1]) - mid
    }

    minPre := 0.0
    for i := k; i <= n; i++ {
        if pre[i-k] < minPre {
            minPre = pre[i-k]
        }
        if pre[i]-minPre >= 0 {
            return true
        }
    }
    return false
}

复杂度分析

时间复杂度：$O(n \log \frac{R}{\varepsilon})$，本实现固定 60 轮迭代故为 $O(60n)$ 即 $O(n)$ 常数较大的线性。凭什么：外层二分次数由值域宽度 $R$ 与精度 $\varepsilon$ 决定且与 n 无关，内层判定只做一次前缀和构造和一次线性扫描。

空间复杂度：$O(n)$。凭什么：每次判定都新建长度 n + 1 的前缀和数组；若把前缀和改成一边扫一边滚动的两个标量，可以进一步降到 $O(1)$，但可读性会下降。

关键点总结

最优化转判定是二分答案的灵魂：当目标量本身不单调、不可增量维护时，「答案是否至少为 x」往往是单调的，把 argmax 换成一串 yes/no 提问就能用二分。

分式约束要线性化：平均值 $\ge x$ 改写成「每项减 x 后区间和 $\ge 0$」，这个手法在最大密度子图、最优比率环（0-1 分数规划 / Dinkelbach）里是同一套思想，属于高价值可迁移技巧。

「区间长度至少为 k 且区间和最大」的标准解法是前缀和 + 延迟解禁的前缀最小值：右端点每前进一步，就把 i - k 这个刚刚合法的左端点并入候选最小值。这个「延迟一拍」的写法在 1031、689 等题里反复出现。

实数二分与整数二分是两套模板：实数二分没有 mid ± 1，终止靠固定轮数或绝对精度，返回可行侧；把整数模板硬套过来轻则精度不足，重则死循环。

面试视角：能主动说清「为什么判定单调」和「为什么减去 mid 之后问题变成子数组和」，比背下代码重要得多；被追问优化时，可以补充「判定内的前缀和可以滚动成 $O(1)$ 空间」。

易错点总结

错误写法：二分下界写成 0；用例 nums = [-1, -2, -3]、k = 2 → 真实答案约 -1.5 落在区间外，二分始终判定为假，最终返回 0 附近的错误值。

错误写法：判定里 minPre 初值设为正无穷或 pre[k]；用例 nums = [4, 0, 4]、k = 3 → 唯一合法区间的左端点是 pre[0] = 0，若不把它纳入最小值候选，判定恒为假，答案被压到区间下界。

错误写法：判定里先检查 pre[i] - minPre >= 0 再更新 minPre；用例 nums = [5, 5]、k = 2 → i = 2 时 pre[0] 尚未纳入，长度恰为 k 的区间被漏判，返回值偏小。

错误写法：把 i - j >= k 误写成 i - j > k；用例 nums = [1, 2]、k = 2 → 长度正好等于 k 的子数组被排除，判定恒假，答案错误。

错误写法：实数二分沿用整数模板写 left = mid + 1；用例任意输入 → 每次跳过 1 的宽度，答案被强行取整，12.75 变成 13 或更离谱的值。

错误写法：终止条件写成 while (left < right) 且用浮点比较；用例任意输入 → 浮点数折半永远不会真正相等，循环不终止直接 TLE。

错误写法：判定成立时写 right = mid、不成立时写 left = mid（方向搞反）；用例 nums = [1, 12, -5, -6, 50, 3]、k = 4 → 二分朝着不可行的方向收敛，最终返回数组最小值附近的值而不是 12.75。

错误写法：不做「减去 mid」的转化，改成枚举右端点并对每个长度重新算平均；用例 $n = 10^4$ → 判定退化成 $O(n^2)$，乘上 60 轮直接超时。

错误写法：用 int 或整型前缀和存放减去 mid 之后的值；用例 nums = [1, 2]、k = 1、mid = 1.5 → 小数部分被截断，判定结果与真实情况不符，二分收敛到错误位置。

错误写法：迭代次数设得太少，例如 20 次；用例值域跨度 $2 \times 10^4$ → 残余误差约 $0.02$，超出 $10^{-5}$ 的容限，被判 WA。

相似题目

题目	难度	考察点
410. 分割数组的最大值	困难	二分的是整数上限，判定用贪心分段计数，无需前缀和转化
875. 爱吃香蕉的珂珂	中等	最基础的整数二分答案，判定只是一次带向上取整的求和
719. 找出第 K 小的数对距离	困难	判定从「存在性」变成「计数是否达标」，内部还要再套一层双指针
1231. 分享巧克力	困难	二分最小值的最大化，判定是贪心切分并检查份数是否够