LeetCode 1423中等滑动窗口/前缀和
可获得的最大点数 图解题解
这道题到底在问什么
卡牌点数数组 cardPoints,每次从开头或末尾取一张,恰好取 k 张,返回最大点数和。
- 输入
- cardPoints=[1,2,3,4,5,6,1], k=3
- 输出
- 12
最优解：一步一步想明白
- 3记住这把钥匙:取两端最大 = 留中间最小。求长度 6 的最小窗口和,再用总和减它。
- 4先把最左边、长度 6 的窗口建起来:把第 0 张(点数 8)加进来,窗口和现在是 8。
- 5先把最左边、长度 6 的窗口建起来:把第 1 张(点数 2)加进来,窗口和现在是 10。
- 6先把最左边、长度 6 的窗口建起来:把第 2 张(点数 3)加进来,窗口和现在是 13。
- 7先把最左边、长度 6 的窗口建起来:把第 3 张(点数 4)加进来,窗口和现在是 17。
- 8先把最左边、长度 6 的窗口建起来:把第 4 张(点数 5)加进来,窗口和现在是 22。
- 9先把最左边、长度 6 的窗口建起来:把第 5 张(点数 1)加进来,窗口和现在是 23。
- 10第一个长度 6 的窗口建好了,和是 23。先把它记成目前最小的 minSum,对应答案 总和 42 减 23 等于 19。接下来窗口整体右滑,找更小的。
- 11窗口往右滑一格。先把右边新进来的第 6 张(点数 6)加进窗口和,变成 29;这时窗口暂时多了一张,下一步要把最左那张吐掉。
- 12再把左边移出的第 0 张(点数 8)从窗口和里减掉,新窗口 [1, 6] 的和是 21。比之前的 minSum 还小,刷新 minSum = 21,答案候选更新成 42 − 21 = 21。
- 13窗口往右滑一格。先把右边新进来的第 7 张(点数 7)加进窗口和,变成 28;这时窗口暂时多了一张,下一步要把最左那张吐掉。
- 14再把左边移出的第 1 张(点数 2)从窗口和里减掉,新窗口 [2, 7] 的和是 26。没有比已有的 minSum 21 更小,minSum 不动。
- 15窗口往右滑一格。先把右边新进来的第 8 张(点数 2)加进窗口和,变成 28;这时窗口暂时多了一张,下一步要把最左那张吐掉。
- 16再把左边移出的第 2 张(点数 3)从窗口和里减掉,新窗口 [3, 8] 的和是 25。没有比已有的 minSum 21 更小,minSum 不动。
- 17窗口往右滑一格。先把右边新进来的第 9 张(点数 4)加进窗口和,变成 29;这时窗口暂时多了一张,下一步要把最左那张吐掉。
- 18再把左边移出的第 3 张(点数 4)从窗口和里减掉,新窗口 [4, 9] 的和是 25。没有比已有的 minSum 21 更小,minSum 不动。
- 19滑完全程,绿色高亮这段长度 6 的窗口和最小、是 21;把它留在中间,其余从两端抽走的点数最多,等于总和 42 减 21,也就是 21。
⚠️ 容易写错的地方
✗ 错：去枚举两端各取几张
✓ 对：转成「留中间长 n−k 的最小段」
两端取法有 k+1 种组合,转成定长最小窗口和一遍就出
✗ 错：每个窗口重新求和
✓ 对：加右减左 O(1) 更新窗口和
重新求和是 O(n·keep),滑动复用是 O(n)
✗ 错：漏了 k == n 的情形
✓ 对：keep == 0 时直接返回总和
全部抽走、中间不留,答案就是总和,别去滑一个空窗口
完整代码（Python / C++ / Java）
Python
from typing import List
class 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 - bestC++
#include <algorithm>
#include <numeric>
#include <vector>
using namespace std;
class Solution {
public:
int maxScore(vector<int>& cardPoints, int k) {
int n = cardPoints.size(), keep = n - k;
int total = accumulate(cardPoints.begin(), cardPoints.end(), 0);
if (keep == 0) return total;
int cur = accumulate(cardPoints.begin(), cardPoints.begin() + keep, 0), best = cur;
for (int i = keep; i < n; ++i) {
cur += cardPoints[i] - cardPoints[i - keep];
best = min(best, cur);
}
return total - best;
}
};Java
import java.util.*;
class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length, keep = n - k, total = 0;
for (int x : cardPoints) total += x;
if (keep == 0) return total;
int cur = 0;
for (int i = 0; i < keep; i++) cur += cardPoints[i];
int best = cur;
for (int i = keep; i < n; i++) {
cur += cardPoints[i] - cardPoints[i - keep];
best = Math.min(best, cur);
}
return total - best;
}
}复杂度
时间
O(n)
求总和一遍 + 定长窗口滑一遍,各线性
空间
O(1)
只用 total / cur / best 几个变量
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 可获得的最大点数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题最妙的一步是什么?+
是「正难则反」的转化:直接枚举两端各取多少张要讨论 k+1 种切法,但反过来看「留下的是中间一段定长连续卡牌」,问题立刻变成最经典的定长最小窗口和,一遍滑窗解决。识别出这层转化是关键。
如果改成求「取走的最小」呢?+
完全对称:取走最小 = 留中间最大,把求最小窗口和换成求最大窗口和即可,其余一模一样。这类「两端取 k 个」的题都能往「中间留定长段」上靠。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 可获得的最大点数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。