博客

题目描述

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

示例：

输入：[1,12,-5,-6,50,3], k = 4

输出：12.75

解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

提示：

1 <= k <= n <= 30,000。

所给数据范围 [-10,000，10,000]。

题目链接：https://leetcode-cn.com/problems/maximum-average-subarray-i

解答

思路一：滑动窗口（窗口大小固定的场景）。

一个数组nums，先算合最大的连续数组，最后再除k。重点变成了计算合最大的连续数组，从index=0l开始遍历，先计算第一个K长度的数组的合sums[0]，然后依次向后遍历，每向后滑动一个此时index为i，重新得到的数组的合为sums[i-1]-nums[i-1]+nums[i+k]，将sums[i]都放到sums数组里，最后使用max(sums)就可以啦

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        sums = []
        sums.append(sum(nums[:k]))
        for i in range(1, len(nums)-k+1):
            sums.append(sums[i-1]-nums[i-1]+nums[i+k-1])
        return max(sums)/k

或

class Solution(object):
    def findMaxAverage(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: float
        """
        return  max([sum(nums[i:i+k]) for i in range(len(nums)-k+1)])/(k*1.0)