题目
难度：★☆☆☆☆
类型：树
给定 n 个整数，找出平均数最大且长度为 k 的连续子数组，并输出该最大平均数。
注意
1 <= k <= n <= 30,000。
所给数据范围 [-10,000，10,000]。
示例
输入: [1,12,-5,-6,50,3], k = 4
输出: 12.75
解释: 最大平均数 (12-5-6+50)/4 = 51/4 = 12.75
解答
由于K是固定的，所以这道题实际上的数组的最大连续子序和的问题，理论上，我们可以尝试直接计算滑窗中的均值：
class Solution:
def findMaxAverage(self, nums, k):
avg = lambda nums: sum(nums) / k # 定义一个求取平均值的函数
max_avg = avg(nums[:k]) # 初始化最大平均值
for i in range(len(nums)-k+1): # 遍历滑窗
cur_avg = avg(nums[i:i+k]) # 计算当前滑窗中的均值
max_avg = max(max_avg, cur_avg) # 更新最大均值
return max_avg # 返回最大均值
但是超时了，我们应该简化思路，由于K是固定的，我们而且相邻滑窗的和是有关系的。这里，我们定义左右指针，分别代表当前滑窗最左端位置以及下一个滑窗的最右端位置，每次上一步元素减去左指针位置元素再加上右指针位置元素即可获得下一个滑窗和，计算量小很多。
class Solution:
def findMaxAverage(self, nums, k):
left, right, cur_sum = 0, k, sum(nums[:k]) # 初始化左右指针和当前滑窗中的元素和
max_sum = cur_sum # 定义当前最大值
while right < len(nums): # 遍历滑窗
cur_sum = cur_sum + nums[right] - nums[left] # 获得当前滑窗中的元素和
max_sum = max(max_sum, cur_sum) # 更新当前最大和
left, right = left + 1, right + 1 # 左右指针右移
return max_sum / k # 返回最大均值
如有疑问或建议，欢迎评论区留言~
