🥉Easy

给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。

示例：

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

提示：

  • 1 <= k <= n <= 30,000。
  • 所给数据范围 [-10,000，10,000]。

题解

这种题就得滑动窗口，单纯的计算遇到很大的数据一定会超时！！！

  1. var findMaxAverage = function(nums, k) {
  2.     let max = -Infinity
  3.     for(let i=0;i<=nums.length-k;i++){
  4.         let temp=nums.slice(i,i+k)
  5.         let sum = temp.reduce((prev,cur)=> prev+cur)/k
  6.         if (sum>max) max=sum
  7.     }
  8.     return max
  10. };

image.png

滑动窗口

JavaScript

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var findMaxAverage = function(nums, k) {
  7.     let data = nums.slice(0,k)
  8.     let sum = data.reduce((prev,cur)=> prev+cur)
  9.     let max = sum/k
  10.     for (let i=1;i<=nums.length-k;i++){
  11.         sum-=nums[i-1]
  12.         sum+=nums[i+k-1]
  13.         if (sum/k > max) max = sum/k
  14.     }
  15.     return max
  17. };

Python

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        maxTotal = total = sum(nums[:k])
        n = len(nums)

        for i in range(k, n):
            total = total - nums[i - k] + nums[i]
            maxTotal = max(maxTotal, total)

        return maxTotal / k

复杂度分析

  • 时间复杂度：🥉643. 子数组最大平均数 I - 图2，其中nn 是数组nums 的长度。遍历数组一次。
  • 空间复杂度：🥉643. 子数组最大平均数 I - 图3。