LeetCode 643 子数组最大平均数 I难度Easy标签数组、定长滑动窗口题号643题目原文给你一个由n个元素组成的整数数组nums和一个整数k。请你找出平均数最大且长度为 k的连续子数组并输出该最大平均数。任何误差小于10−510^{-5}10−5的答案都将被视为正确答案。示例1输入nums [1,12,-5,-6,50,3], k 4输出12.75解释最大平均数(12−5−650)/451/412.75(12-5-650)/4 51/4 12.75(12−5−650)/451/412.75示例2输入nums [5], k 1输出5.00000约束条件nnums.lengthn nums.lengthnnums.length1≤k≤n≤1051 \le k \le n \le 10^51≤k≤n≤105−104≤nums[i]≤104-10^4 \le nums[i] \le 10^4−104≤nums[i]≤104费曼学习法讲解破解过程像讲给小白第一步大白话翻译题目我们有一串连续数字要求连续k个数字的一段子数组算出这一段的平均值找到平均值最大的那一组返回这个平均值。关键点子数组必须连续长度严格等于k不能多不能少。技巧比较平均值等价于比较总和。因为所有候选子数组都除以同一个k哪个子数组总和最大平均值就一定最大。我们只需要找最大和最后一次性除以k即可全程减少浮点数运算。第二步思考两种解法对比优劣解法1暴力枚举直观但大数据超时思路遍历数组所有起点每一个起点取连续k个数循环k次求和记录最大总和。时间复杂度O(n∗k)O(n*k)O(n∗k)问题题目数组最长10510^5105如果k很大1e5*1e5100亿次运算直接超时。✅优点好理解❌致命缺点大数据量性能爆炸。举例 nums[1,12,-5,-6,50,3],k4起点01,12,-5,-6 → sum2起点112,-5,-6,50 → sum51起点2-5,-6,50,3 → sum42最大sum51平均12.75解法2定长滑动窗口最优解面试标准答案核心思想相邻两个窗口大部分元素是重叠的窗口向右挪一格丢掉窗口最左边的旧数字纳入窗口右边新增的数字。不需要全部重新加一遍一次加减就更新窗口总和。步骤拆解先算出第一个窗口前k个数的总和记为window_sum同时初始化max_sum等于这个和从第k号下标开始循环窗口往右移动window_sum window_sum 新进来右边数字 - 窗口左边被踢出去的数字更新max_sum如果当前窗口总和更大就替换遍历结束最大平均值 max_sum / k时间复杂度O(n)O(n)O(n)数组只遍历一遍空间复杂度O(1)O(1)O(1)只用几个变量不额外开辟数组本题标准最优解能通过全部测试用例支持10万长度数组。第三步找坑点费曼复盘易错点坑1不要每次循环都计算平均值多次浮点运算带来精度损失最后再除以k。坑2数组元素可以是负数max_sum初始化不能写0要等于第一个窗口和。坑3子数组必须连续不是随便挑k个数字。坑4返回浮点数Python除法/自动返回float不要用整数除法//。第四步现实应用场景举例服务器CPU监控采集每秒CPU使用率数组求连续5秒窗口的平均CPU峰值用于告警股票数据获取每日收盘价求连续20天均线最大值定长滑动窗口传感器采集IoT数据温度传感器每秒上报数值找连续10秒的最高平均温度视频码率统计按帧统计码率计算连续k帧的平均码率定位码率突增片段。本质流式时序数据固定窗口大小求统计值滑动窗口是时序数据分析基础模板。Python代码1暴力枚举带详细注释仅用于理解大数据超时fromtypingimportListclassSolution:deffindMaxAverage(self,nums:List[int],k:int)-float:# 获取数组总长度nlen(nums)# 初始化最大和负无穷防止数组全负数场景max_sumfloat(-inf)# 遍历所有合法窗口起点起点最大 n-kforstartinrange(n-k1):# 当前窗口总和初始化为0current_sum0# 从起点开始累加连续k个数字foroffsetinrange(k):current_sumnums[startoffset]# 如果当前窗口总和大于记录的最大值则更新ifcurrent_summax_sum:max_sumcurrent_sum# 最大总和除以k得到最大平均值returnmax_sum/k# 测试代码if__name____main__:solSolution()print(sol.findMaxAverage([1,12,-5,-6,50,3],4))#输出12.75print(sol.findMaxAverage([5],1))#输出5.0Python代码2滑动窗口最优解法每行详细注释推荐fromtypingimportListclassSolution:deffindMaxAverage(self,nums:List[int],k:int)-float: Leetcode643 子数组最大平均数 I定长滑动窗口 :param nums: 原始整数数组 :param k: 子数组固定长度 :return: 长度k的连续子数组最大平均值 # 第一步计算第一个窗口前k个元素总和window_sumsum(nums[:k])# 初始化最大总和就是第一个窗口的值max_sumwindow_sum# 从下标k开始遍历数组新元素进入窗口# i代表当前新加入窗口的元素下标foriinrange(k,len(nums)):# 更新窗口总和加上右侧新进来数字减去窗口最左侧移出的数字# i-k 就是被踢出窗口的那个元素下标window_sumwindow_sumnums[i]-nums[i-k]# 判断当前窗口总和是否超过历史最大值如果是更新最大值ifwindow_summax_sum:max_sumwindow_sum# 全部窗口遍历完毕最大总和除以k得到最大平均值returnmax_sum/k# 测试用例 if__name____main__:objSolution()test1obj.findMaxAverage([1,12,-5,-6,50,3],4)print(f测试用例1结果{test1})#预期输出12.75test2obj.findMaxAverage([5],1)print(f测试用例2结果{test2})#预期输出5.0test3obj.findMaxAverage([-1,-2,-3,-4],2)print(f测试用例3结果{test3})#(-1-2)-3, (-2-3)-5, (-3-4)-7 → 最大平均-1.5Python代码3前缀和版本额外解法拓展理解前缀和思路预先构建前缀数组pre_sumpre_sum[i]代表前i个元素总和区间[left,right]和 pre_sum[right1] - pre_sum[left]fromtypingimportListclassSolution:deffindMaxAverage(self,nums:List[int],k:int)-float:nlen(nums)# 前缀和数组pre_sum[0]0, pre_sum[1]nums[0], pre_sum[2]nums[0]nums[1]pre_sum[0]*(n1)foriinrange(n):pre_sum[i1]pre_sum[i]nums[i]max_sumfloat(-inf)# 遍历所有窗口起点forstartinrange(n-k1):endstartk-1# 窗口和 pre_sum[end1] - pre_sum[start]window_sumpre_sum[end1]-pre_sum[start]ifwindow_summax_sum:max_sumwindow_sumreturnmax_sum/k#测试if__name____main__:solSolution()print(sol.findMaxAverage([1,12,-5,-6,50,3],4))前缀和时间O(n)空间O(n)滑动窗口原地O(1)空间工程优先滑动窗口。复杂度总结暴力时间O(nk)空间O(1)大数据超时滑动窗口时间O(n)空间O(1)最优前缀和时间O(n)空间O(n)适合拓展到不定长区间求和问题。费曼总结这道题是定长滑动窗口模板题核心一句话固定大小窗口移动时不用重复计算全部窗口只更新进出窗口的元素贡献把复杂度从n*k压缩到n。这个模板可以迁移到大量同类题目固定窗口求最大值、最小值、计数。