【力扣日记】643 子数组最大平均值

题目描述

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

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

算法思路

暴力

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

超时了。

滑动窗口

很显然可以分析得到，对每一个i，都求了一次和。
显然从index：0—>1，子数组的和增加了50，减少了1，进而，每次只减去丢掉值，加上增加的值，然后对比当前记录的最大值即可。

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

执行用时 :1060 ms, 在所有 Python3 提交中击败了63.21%的用户
内存消耗 :17.3 MB, 在所有 Python3 提交中击败了5.24%的用户