题目描述:
给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。
请你找出平均数最大且 长度为 k 的连续子数组,并输出该最大平均数。
任何误差小于 10-5 的答案都将被视为正确答案。
示例输入:
输入:nums = [1,12,-5,-6,50,3], k = 4
输出:12.75
解释:最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
解题思路分析:
要点分析:滑动窗口的思路
step1:找出其中一个长度为k的连续子数组
第一个子数组的元素和sumk-1 需要计算nums的前k个元素之和得到
遍历数组nums一次即可得到
依次计算第二个子数字的元素和sumk(推演过程)
step2:求出该连续子数组的k项和
用sumi表示数组以下标i结尾的长度为k的子数组的元素和,i>=k-1,其中子数组的个数为 n-k+1个
维护一个长度为k的滑动窗口,当窗口从下标范围[i-k,i-1],移动到[i-k+,i]时,nums [i-k]从窗口移除,nums[i]从窗口进入
step3:写循环,求出所有连续子数组k项和的最大值
step4:输出最大值的平均数
解题代码如下:
class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
#用数组total将nums中任意取的k个连续的子数组存起来
maxTotal = total = sum(nums(:k))
n = len(nums)
#对i从k到n-1进行遍历(总共有n-k+1个子数组)
for i in range(k,n):
total = total -nums[i-k] + mums[i]
matotal = max(maxTotal,totla)
return maxTotal / k