目录LeetCode 643. 子数组最大平均数 I从暴力枚举到滑动窗口一、最开始的思路枚举每一个长度为 k 的子数组二、发现问题相邻窗口其实有大量重复内容三、什么是滑动窗口1. 定长滑动窗口一般怎么做2. 怎么判断一道题适不适合滑动窗口四、回到这道题怎么修改原来的代码为什么循环条件是 i n-k五、还能进一步简化吗六、复杂度分析七、最后复盘LeetCode 643. 子数组最大平均数 I从暴力枚举到滑动窗口题目链接643. 子数组最大平均数 I弄了个网站, 可以看代码是怎么操作达到最终要的结果: 过程可视化一、最开始的思路枚举每一个长度为 k 的子数组题目要求找到一个长度为k的连续子数组使它的平均值最大。我最开始的想法很直接既然要求最大平均值那就把所有长度为k的连续子数组都找出来分别计算平均值再取最大的那个。于是就这样写出了第一版classSolution:deffindMaxAverage(self,nums:list[int],k:int)-float:nlen(nums)max_mean-float(inf)i0whilein-k:current0jiwhilejik:currentnums[j]j1max_meanmax(current/k,max_mean)i1returnmax_mean这里两个while分别负责外层枚举每一个合法的子数组起点i。内层计算从i开始、长度为k的子数组总和。例如nums [1, 12, -5, -6, 50, 3] k 4 第一个窗口[1, 12, -5, -6] 第二个窗口[12, -5, -6, 50] 第三个窗口[-5, -6, 50, 3]这个思路没有问题但每次移动到下一个位置都需要重新累加k个数字。一共有n-k1个窗口每个窗口需要O(k)的求和时间。因此时间复杂度是O((n-k1) × k)通常记为O(nk)。因此当数组很长、k也很大时就容易超出时间限制。。。那么有没有办法避免重复计算二、发现问题相邻窗口其实有大量重复内容观察前两个窗口第一个[ 1, 12, -5, -6] 第二个[12, -5, -6, 50]它们中间的12、-5、-6完全一样。但我之前的代码每次都会current0然后重新计算整个窗口的总和。既然大部分数字没有变化为什么不直接利用上一个窗口已经计算出来的结果例如第一个窗口总和1 12 - 5 - 6 2向右移动一格以后移出左边的 1 加入右边的 50 新窗口总和 2 - 1 50 51这样就不需要重新计算中间的三个数字了。所以关键的变化是不再每次重新计算窗口而是维护一个可以随着窗口移动而更新的总和。这就引出了滑动窗口。三、什么是滑动窗口简单来说滑动窗口Sliding Window是一种处理数组或字符串中连续区间的常见算法思想。可以把窗口理解成一个框框住当前需要处理的一段连续元素。随着窗口向右移动我们不必每次重新处理框里的所有内容而是尽量利用之前已经计算过的信息。推荐去我的网站看看 有过程的可视化 会更好的理解滑动窗口的窗长什么样怎么运动的~例如固定长度为3nums [1, 2, 3, 4, 5] [1, 2, 3] 4 5 1 [2, 3, 4] 5 1 2 [3, 4, 5]滑动窗口通常分为两种类型特点常见问题定长滑动窗口窗口长度固定每次整体移动长度为 k 的最大总和、平均值不定长滑动窗口窗口长度可以变化根据条件扩张或收缩满足条件的最短或最长子数组这道 643 题属于定长滑动窗口。1. 定长滑动窗口一般怎么做通常可以分成四步第一步确定窗口长度。例如题目要求长度为k那窗口始终包含k个元素。第二步初始化第一个窗口。先计算前k个元素的总和currentsum(nums[:k])第三步移动窗口更新状态。每次窗口右移一格旧窗口[a, b, c] 新窗口[b, c, d] 移出 a 移入 d所以新窗口和 旧窗口和 - 移出元素 移入元素第四步更新答案。每移动一次就根据题目要求更新最大值、最小值或其他统计结果。需要注意的是滑动窗口不一定维护总和。根据题目不同也可能维护字符出现次数、不同元素的数量等状态。它的核心是窗口移动时只处理发生变化的部分尽量复用原来的计算结果。2. 怎么判断一道题适不适合滑动窗口可以先观察三个问题题目是不是在研究数组或字符串中的连续区间是不是需要不断考察相邻的区间当区间移动时能不能通过加入、移除元素来高效更新需要的信息如果这些条件都满足就值得考虑滑动窗口。但不是所有连续区间题都能直接套用同一种滑动窗口写法尤其是不定长窗口还需要考虑窗口收缩是否具有正确性依据。四、回到这道题怎么修改原来的代码我原来使用i表示窗口的起始位置。所以继续保留这个定义。例如k 4i 0 窗口下标[0, 1, 2, 3] i 1 窗口下标[1, 2, 3, 4]从第一个窗口移动到第二个窗口移出的下标0 i - 1 移入的下标4 i k - 1因此只需要更新currentcurrent-nums[i-1]nums[ki-1]但第一个窗口比较特殊。因为它前面没有旧窗口可以复用所以必须先计算一次ifi0:currentsum(nums[:k])之后的窗口才使用更新公式。于是得到第二版代码classSolution:deffindMaxAverage(self,nums:list[int],k:int)-float:nlen(nums)max_mean-float(inf)i0whilein-k:ifi0:currentsum(nums[:k])else:currentcurrent-nums[i-1]nums[ki-1]max_meanmax(current/k,max_mean)i1returnmax_mean这次不再需要内层while。因为每次窗口移动只需要一次减法和一次加法就能得到新的窗口总和。为什么循环条件是i n-k因为i表示窗口起点。一个长度为k的窗口最右边的下标是i k - 1它不能超过数组最后一个下标n-1。因此i k - 1 n - 1 i n - k五、还能进一步简化吗其实可以。因为所有窗口的长度都是k而且k是固定的正数。所以总和越大平均值就越大。我们没有必要每次都除以k可以先找到最大的窗口总和最后再计算平均值。另外第一个窗口也可以在循环外初始化这样就不需要每次判断i 0。classSolution:deffindMaxAverage(self,nums:list[int],k:int)-float:nlen(nums)currentsum(nums[:k])max_sumcurrentforiinrange(1,n-k1):currentcurrent-nums[i-1]nums[ik-1]max_summax(max_sum,current)returnmax_sum/k这版和我自己写的第二版本质上是同一种算法只是把初始化和循环分开让代码更加简洁。六、复杂度分析最开始的暴力枚举时间复杂度O((n-k1)k)通常简写为O(nk)。空间复杂度O(1)。优化后的滑动窗口时间复杂度O(n)。初始化需要O(k)之后每次窗口移动只需要O(1)。空间复杂度O(1)。只需要维护当前窗口总和和最大值等变量。七、最后复盘这道题的思考过程其实很简单题目要求长度为 k 的最大平均值 ↓ 先枚举所有长度为 k 的连续子数组 ↓ 每次重新计算窗口总和 ↓ 发现相邻窗口有大量重复元素 ↓ 既然大部分元素没变能不能复用旧结果 ↓ 窗口右移时只移出一个、加入一个 ↓ 维护窗口总和 ↓ 从 O(nk) 优化到 O(n)可以通过这道题去理解定长滑动窗口的作用滑动窗口不是简单地把双层循环改成单层循环而是通过维护窗口状态避免对相邻区间进行重复计算。以后遇到类似题目可以先问当这个连续区间向右移动时究竟哪些元素发生了变化之前的计算结果能不能直接利用如果能找到高效更新状态的方法就有机会使用滑动窗口优化。