题目描述
思路解析动画文字版
记住这把钥匙:取两端最大 = 留中间最小。求长度 6 的最小窗口和,再用总和减它。
先把最左边、长度 6 的窗口建起来:把第 0 张(点数 8)加进来,窗口和现在是 8。
先把最左边、长度 6 的窗口建起来:把第 1 张(点数 2)加进来,窗口和现在是 10。
先把最左边、长度 6 的窗口建起来:把第 2 张(点数 3)加进来,窗口和现在是 13。
先把最左边、长度 6 的窗口建起来:把第 3 张(点数 4)加进来,窗口和现在是 17。
先把最左边、长度 6 的窗口建起来:把第 4 张(点数 5)加进来,窗口和现在是 22。
先把最左边、长度 6 的窗口建起来:把第 5 张(点数 1)加进来,窗口和现在是 23。
第一个长度 6 的窗口建好了,和是 23。先把它记成目前最小的 minSum,对应答案 总和 42 减 23 等于 19。接下来窗口整体右滑,找更小的。
窗口往右滑一格。先把右边新进来的第 6 张(点数 6)加进窗口和,变成 29;这时窗口暂时多了一张,下一步要把最左那张吐掉。
再把左边移出的第 0 张(点数 8)从窗口和里减掉,新窗口 [1, 6] 的和是 21。比之前的 minSum 还小,刷新 minSum = 21,答案候选更新成 42 − 21 = 21。
窗口往右滑一格。先把右边新进来的第 7 张(点数 7)加进窗口和,变成 28;这时窗口暂时多了一张,下一步要把最左那张吐掉。
再把左边移出的第 1 张(点数 2)从窗口和里减掉,新窗口 [2, 7] 的和是 26。没有比已有的 minSum 21 更小,minSum 不动。
窗口往右滑一格。先把右边新进来的第 8 张(点数 2)加进窗口和,变成 28;这时窗口暂时多了一张,下一步要把最左那张吐掉。
再把左边移出的第 2 张(点数 3)从窗口和里减掉,新窗口 [3, 8] 的和是 25。没有比已有的 minSum 21 更小,minSum 不动。
窗口往右滑一格。先把右边新进来的第 9 张(点数 4)加进窗口和,变成 29;这时窗口暂时多了一张,下一步要把最左那张吐掉。
再把左边移出的第 3 张(点数 4)从窗口和里减掉,新窗口 [4, 9] 的和是 25。没有比已有的 minSum 21 更小,minSum 不动。
滑完全程,绿色高亮这段长度 6 的窗口和最小、是 21;把它留在中间,其余从两端抽走的点数最多,等于总和 42 减 21,也就是 21。
边界先想清:k=n 取全部、k=1 取首尾较大者、单元素取它本身。
面试常考:讲清「两端取 → 中间留定长段」的转化,以及它的对称变体。
参考代码
from typing import Listclass Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: n = len(cardPoints) keep = n - k if keep == 0: return sum(cardPoints) total = sum(cardPoints) cur = sum(cardPoints[:keep]) best = cur for i in range(keep, n): cur += cardPoints[i] - cardPoints[i - keep] best = min(best, cur) return total - best复杂度
- 时间：O(n)，求总和一遍 + 定长窗口滑一遍,各线性
- 空间：O(1)，只用 total / cur / best 几个变量
易错点
面试追问把动画讲成自己的话
追问这道题最妙的一步是什么?
追问如果改成求「取走的最小」呢?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
绝对差不超过限制的最长连续子数组
LeetCode 1438 · 中等 · 沿着 滑动窗口套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题