题目
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
一、代码实现
func findMaxAverage(nums []int, k int) float64 {currentSum := 0// 计算初始窗口和for i := 0; i < k; i++ {currentSum += nums[i]}maxSum := currentSum// 滑动窗口遍历for i := k; i < len(nums); i++ {currentSum += nums[i] - nums[i-k] // 窗口右移，更新当前和if currentSum > maxSum {maxSum = currentSum}}return float64(maxSum) / float64(k)
}
二、算法分析
-
核心思路
- 滑动窗口策略：通过维护一个固定长度为k的窗口，在O(n)时间内遍历所有候选子数组
- 增量计算：每次窗口移动只需加减两个元素，避免重复求和计算
- 极值追踪：实时更新最大和值，最后统一计算平均数
-
关键步骤
-
初始化窗口：计算前k个元素的和作为初始窗口和
-
窗口滑动：每次右移窗口时，加上新进入元素，减去退出的左侧元素
-
极值比较：立即比较当前窗口和与历史最大值
-
结果转换：将最终最大和转换为浮点数求平均
-
复杂度
- 时间复杂度：
O(n)，完整遍历数组一次 - 空间复杂度：
O(1)，仅使用固定变量存储和值
- 时间复杂度：
三、图解
四、边界条件与扩展
-
特殊场景处理
- k=1时：等价于寻找数组最大元素
- 全负数数组：算法仍能正确找到相对最大值（如[-3,-1,-2],k=2 → -1.5）
- k等于数组长度：直接计算整个数组的平均值
-
多语言实现
# Python实现（滑动窗口）
def findMaxAverage(nums, k):window_sum = sum(nums[:k])max_sum = window_sumfor i in range(k, len(nums)):window_sum += nums[i] - nums[i-k]max_sum = max(max_sum, window_sum)return max_sum / k
// Java实现（空间优化）
public double findMaxAverage(int[] nums, int k) {int sum = 0;for(int i=0; i<k; i++) sum += nums[i];int maxSum = sum;for(int i=k; i<nums.length; i++){sum += nums[i] - nums[i-k];maxSum = Math.max(maxSum, sum);}return maxSum * 1.0 / k;
}
- 算法对比
| 方法 | 时间复杂度 | 空间复杂度 | 优势 |
|---|---|---|---|
| 滑动窗口法 | O(n) | O(1) | 最优解，推荐实现 |
| 前缀和法 | O(n) | O(n) | 预处理后支持随机查询 |
| 暴力枚举 | O(nk) | O(1) | 仅适用于极小数据量 |
五、总结
- 核心创新：将传统O(nk)暴力法优化为O(n)线性算法，通过窗口滑动实现高效增量计算
- 数学证明：设数组长度为n，滑动窗口共进行(n-k)次移动，完整覆盖所有可能子数组
- 优化亮点：
- 消除重复计算，每次窗口更新仅需两次算术运算
- 整数运算避免浮点精度损失，最后统一转换结果
- 适用场景：实时数据流分析、大规模时序数据处理等需要高效计算的场景
