题目描述
思路解析动画文字版
核心就一句:窗口右移一格 = 加新进的、减滑出的。和是边滑边更新的,全程只扫一遍。
先搭起始窗口:把下标 0 到 0 的数加起来,目前窗口和是 1。继续往右凑够 k 个。
先搭起始窗口:把下标 0 到 1 的数加起来,目前窗口和是 13。继续往右凑够 k 个。
先搭起始窗口:把下标 0 到 2 的数加起来,目前窗口和是 8。继续往右凑够 k 个。
先搭起始窗口:把下标 0 到 3 的数加起来,目前窗口和是 2。前 k 个数凑齐了。
起始窗口(高亮这 k 个)的和是 2,先把它当成目前见过的最大窗口和。接下来窗口开始向右滑。
窗口准备向右滑一格。标红的下标 0(值 1)马上要滑出窗口,绿色的下标 4(值 50)马上要进窗口。
窗口滑到下标 1~4。新和 = 旧和 2 + 进的 50 − 出的 1 = 51。这比之前的最大还大,记下它。
窗口准备向右滑一格。标红的下标 1(值 12)马上要滑出窗口,绿色的下标 5(值 3)马上要进窗口。
窗口滑到下标 2~5。新和 = 旧和 51 + 进的 3 − 出的 12 = 42。没超过当前最大 51,最大值不变。
窗口准备向右滑一格。标红的下标 2(值 -5)马上要滑出窗口,绿色的下标 6(值 -2)马上要进窗口。
窗口滑到下标 3~6。新和 = 旧和 42 + 进的 -2 − 出的 -5 = 45。没超过当前最大 51,最大值不变。
窗口准备向右滑一格。标红的下标 3(值 -6)马上要滑出窗口,绿色的下标 7(值 7)马上要进窗口。
窗口滑到下标 4~7。新和 = 旧和 45 + 进的 7 − 出的 -6 = 58。这比之前的最大还大,记下它。
窗口准备向右滑一格。标红的下标 4(值 50)马上要滑出窗口,绿色的下标 8(值 4)马上要进窗口。
窗口滑到下标 5~8。新和 = 旧和 58 + 进的 4 − 出的 50 = 12。没超过当前最大 58,最大值不变。
窗口准备向右滑一格。标红的下标 5(值 3)马上要滑出窗口,绿色的下标 9(值 -1)马上要进窗口。
窗口滑到下标 6~9。新和 = 旧和 12 + 进的 -1 − 出的 3 = 8。没超过当前最大 58,最大值不变。
窗口准备向右滑一格。标红的下标 6(值 -2)马上要滑出窗口,绿色的下标 10(值 8)马上要进窗口。
窗口滑到下标 7~10。新和 = 旧和 8 + 进的 8 − 出的 -2 = 18。没超过当前最大 58,最大值不变。
窗口准备向右滑一格。标红的下标 7(值 7)马上要滑出窗口,绿色的下标 11(值 2)马上要进窗口。
窗口滑到下标 8~11。新和 = 旧和 18 + 进的 2 − 出的 7 = 13。没超过当前最大 58,最大值不变。
滑完整趟,所有长度 4 的窗口里和最大的是高亮这一段(和 58)。最大平均 = 58 ÷ 4 = 14.5,就是答案。
三个高频追问:复杂度从哪降、和怎么增量更新、有负数怎么办。
参考代码
def findMaxAverage(nums, k): s = sum(nums[:k]) # 起始窗口和 best = s for r in range(k, len(nums)): s += nums[r] - nums[r-k] # 加新进的、减滑出的 best = max(best, s) return best / k复杂度
- 时间:O(n),凑起始窗口扫 k 个,之后每滑一格只做一加一减,整体一趟扫过数组
- 空间:O(1),只用窗口和 s 与最大值 best 两个变量,不开额外数组
易错点
面试追问把动画讲成自己的话
追问滑动窗口为什么比暴力快?
追问窗口和更新时为什么是「加 nums[r] 减 nums[r-k]」?
追问如果数组里有负数会影响做法吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
无重复字符的最长子串
LeetCode 3 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题