LeetCode 643. 子数组最大平均数 I
题目描述
题意分析
在数组中选择长度恰好为
k的连续子数组，返回最大的平均值。元素可以为负数，不能用空子数组代替长度要求；题目保证1 <= k <= nums.length。
解法：滑动窗口维护有效区间
核心思路
[!blue]
所有候选长度都相同，比较平均值就等价于比较窗口和。 分母k为固定正数，因此先求最大的窗口和maxSum，最后除以k即可，不必为每个窗口重复计算平均值。先求下标
[0, k - 1]的和，作为sum和maxSum的初值。从i = k开始，每轮加入nums[i]、移出nums[i - k]，更新后sum恰好表示窗口[i - k + 1, i]的和。相邻窗口中间的k - 1项相同，只调整两端即可完成移动。每次移动完成后更新
maxSum，它始终是所有已检查完整窗口中的最大和。第一个窗口由初始化覆盖，其余窗口各对应一个新的右端点，因此没有遗漏。必须用真实首窗初始化最大值，全部元素为负时，0 可能根本不是任何合法窗口的和。最后先转成浮点数，再除以
k，保留平均值的小数部分。k = 1时相当于寻找最大元素，k = n时只有初始窗口，滑动循环不执行也能直接返回结果。
解题步骤
- 计算前 k 项之和，并初始化最大和。
- 从下标 k 开始，加当前项、减 i-k 位置的项。
- 更新最大和。
- 转为浮点数后除以 k。
代码实现
class Solution {
public double findMaxAverage(int[] nums, int k) {
int n = nums.length;
long sum = 0;
for (int i = 0; i < k; i++) {
sum += nums[i];
}
// 以真实首窗初始化最大值，全部为负时也能正确比较。
long maxSum = sum;
for (int i = k; i < n; i++) {
// 加入当前项并移出旧左端，保持窗口长度固定。
sum += nums[i] - nums[i - k];
if (sum > maxSum) {
maxSum = sum;
}
}
return maxSum * 1.0 / k;
}
}
func findMaxAverage(nums []int, k int) float64 {
sum := 0
for i := 0; i < k; i++ {
sum += nums[i]
}
// 以真实首窗初始化最大值，全部为负时也能正确比较。
maxSum := sum
for i := k; i < len(nums); i++ {
// 加入当前项并移出旧左端，保持窗口长度固定。
sum += nums[i] - nums[i-k]
if sum > maxSum {
maxSum = sum
}
}
return float64(maxSum) / float64(k)
}
复杂度分析
- 时间复杂度：$O(n)$，初始化与滑动合计线性。
- 空间复杂度：$O(1)$，只维护当前和与最大和。
关键点总结
[!green]
- 移出的是 i-k，不是新窗口左端 i-k+1。
- 候选在加减完成后比较。
- 最终转为浮点除法，避免整数截断。
易错点总结
[!yellow]
- 最大和初始化零：全负输入会返回不存在的候选。
- 只加入不移出：统计变成增长前缀。
- 移出位置偏一：不再代表真实定长窗口。
- 先做整数除法再转换：小数部分已经丢失。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 644. 子数组最大平均数 II | 困难 | 本题长度恰为k，滑动维护总和即可；原题长度至少k，不能用单个固定窗口解决。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！