LeetCode 644. 子数组最大平均数 II
题目描述
题意分析
求长度至少为
k的连续子数组的最大平均值，允许按题目精度返回近似结果。候选长度可以不同，最大和不一定对应最大平均值，也不能只检查长度恰好为k的窗口。
解法：二分平均值 + 前缀和可行性检查
核心思路
[!blue]
二分平均值，将最优化转换为可行性判断。 对候选值 $x$，检查是否存在长度至少为 $k$、平均值不小于 $x$ 的子数组。如果 $x$ 可行，所有更小的值也可行；如果 $x$ 不可行，更大的值同样不可行，因此可以二分这个分界。任何子数组的平均值都在数组最小值与最大值之间，用它们初始化上下界，也能覆盖全负数组。对长度为 $L$ 的区间，平均值至少为 $x$ 等价于元素和至少为 $Lx$，也就是将每个元素减去 $x$ 后，区间和非负。由此构建变换后的前缀和
pre，其中pre[i]表示前 $i$ 项之和，pre[0] = 0。固定右端前缀位置 $i$，子数组
[j, i)的长度是 $i-j$，合法左端必须满足 $0\le j\le i-k$。其变换后总和为pre[i] - pre[j]，因此只要取合法范围内最小的pre[j]，就得到了以该右端结束的最大区间和。若这个最大值仍小于 0，其他合法左端也都不可能成功。右端递增时，合法左端范围只会扩展。用
minPre保留此前最小值，并在本轮先纳入刚变合法的pre[i - k]，再检查pre[i] - minPre >= 0。这覆盖了所有长度至少为 $k$ 的区间；先更新再检查，才能包含长度恰好为 $k$ 的候选。任意右端通过就返回真，全部失败才返回假。判定可行时把下界提高到中点，否则把上界降低到中点，最后返回下界。理想计算中，60 轮会将初始区间宽度缩小到原来的 $2^{-60}$；实际浮点数接近时，中点可能与某个端点相同，固定轮数仍能保证结束，不依赖两端最终严格相等。
解题步骤
- 用数组最小、最大元素建立答案范围。
- 每轮将元素减去候选平均值并构建前缀和。
- 维护长度条件允许的历史最小前缀，检查是否存在非负区间。
- 可行则提高下界，否则降低上界，固定轮数后返回下界。
代码实现
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)$，总计 $O(60n)$。
- 空间复杂度：$O(n)$，保存每轮前缀和。
关键点总结
[!green]
- 合法左端是所有不超过 i-k 的前缀位置。
- 候选平均值减到每个元素上后，判定只需区间和。
- 实数二分只移动到 mid，不使用 mid±1。
pre[0]保留了从数组开头出发的区间；k = n时只有整个数组一个候选，也由相同判定覆盖。
易错点总结
[!yellow]
- 下界固定零：全部负数时可能排除真实答案。
- 只检查长度恰好 k：更长区间也属于候选。
- 漏掉刚合法的前缀位置：可能漏掉恰好长度为 k 的最优区间。
- 变换后的前缀使用整数存储：丢失候选平均值带来的小数信息。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 643. 子数组最大平均数 I | 简单 | 长度固定时平均值与总和等价，本题允许不同长度，需另行判定平均值阈值。 |
| 862. 和至少为 K 的最短子数组 | 困难 | 同样在可负的前缀和中判断区间条件，本题先减去候选平均值，再检查长度至少k的非负和区间。 |