Easy

题目描述

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k。

请你找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被接受。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4
输出：12.75000
解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1
输出：5.00000

提示：

  • n == nums.length
  • 1 <= k <= n <= 10^5
  • -10^4 <= nums[i] <= 10^4

解题思路

解题思路

这是一道典型的滑动窗口问题。我们需要找到长度固定为 k 的连续子数组中平均值最大的那个。

方法一：滑动窗口（推荐）

由于子数组长度固定，我们可以用滑动窗口技术来优化计算：

  1. 初始化：先计算前 k 个元素的和作为第一个窗口
  2. 滑动窗口：从第 k+1 个元素开始，每次向右移动窗口，移除左端元素，添加右端元素
  3. 更新最大值：在滑动过程中维护最大子数组和
  4. 返回结果：最大和除以 k 即为最大平均值

这种方法避免了重复计算，时间复杂度为 O(n)。

方法二：暴力法

遍历所有可能的长度为 k 的子数组，计算每个子数组的和，找出最大值。时间复杂度为 O(n×k)，在数据量大时效率较低。

滑动窗口是处理固定大小子数组问题的经典技巧，推荐掌握。

代码实现

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        // 计算前k个元素的和
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }
        
        int maxSum = sum;
        
        // 滑动窗口：移除左端，添加右端
        for (int i = k; i < nums.size(); i++) {
            sum = sum - nums[i - k] + nums[i];
            maxSum = max(maxSum, sum);
        }
        
        return (double)maxSum / k;
    }
};

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        # 计算前k个元素的和
        current_sum = sum(nums[:k])
        max_sum = current_sum
        
        # 滑动窗口：移除左端，添加右端
        for i in range(k, len(nums)):
            current_sum = current_sum - nums[i - k] + nums[i]
            max_sum = max(max_sum, current_sum)
        
        return max_sum / k

public class Solution {
    public double FindMaxAverage(int[] nums, int k) {
        // 计算前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 = sum - nums[i - k] + nums[i];
            maxSum = Math.Max(maxSum, sum);
        }
        
        return (double)maxSum / k;
    }
}

var findMaxAverage = function(nums, k) {
    // 计算前k个元素的和
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }
    
    let maxSum = sum;
    
    // 滑动窗口：移除左端，添加右端
    for (let i = k; i < nums.length; i++) {
        sum = sum - nums[i - k] + nums[i];
        maxSum = Math.max(maxSum, sum);
    }
    
    return maxSum / k;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(n)需要遍历数组一次，其中 n 是数组长度
空间复杂度O(1)只使用常数额外空间

相关题目