当前位置：首页 > article >正文

LeetCode算法题(Go语言实现)_14

article 2025/4/2 2:48:50

题目

给你一个由 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_sum
    for 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;
}