LeetCode 1423. 可获得的最大点数
目录
题目描述
题意分析
给定一排牌
cardPoints，每张牌有一个点数。你要恰好拿走k张牌，但每次只能从这一排的最左端或最右端取，取走后相邻的牌成为新的端点。问所有取法中，拿到的点数之和最大是多少。"只能从两端取"这个限制是全题的题眼。它意味着你的取牌序列虽然可以在左右之间任意穿插，但最终结果只取决于左边取了多少张、右边取了多少张——先左后右还是左右交替，拿到的是同一批牌，点数和完全一样。所以取牌顺序不该进入状态，真正的自由度只有一个变量。
把视角从"拿走了什么"翻到"剩下了什么"会更清爽：左边拿走一段前缀、右边拿走一段后缀，剩下的必然是中间一段连续的牌，而且长度被死死钉在
n - k上，不多不少。这就把一个看似要做选择的问题，变成了在所有定长连续区间里挑一个的问题。约束里
1 ≤ k ≤ n ≤ 10^5，k可以一直取到n。这条上界提示两件事：一是 $O(n^2)$ 的做法必然超时，只能接受线性或线性对数；二是k == n时中间什么都不剩，是一个必须单独看一眼的退化情况。点数范围1 ≤ cardPoints[i] ≤ 10^4，最坏总和是10^9，还在 32 位整数范围内，不会溢出。边界还有一处：
k也可以等于1，此时只在首尾两张里挑大的；而窗口长度n - k最大是n - 1，永远不会等于n，这个性质后面会用到。
解法：反向思考保留最小中间窗口
核心思路
先看暴力。既然结果只由"左边取
i张、右边取k - i张"决定，那就枚举i从0到k，每次现算这两段的和，取最大值。这样是 $O(k^2)$，k取到10^5时约10^10次运算，超时。瓶颈在于每次都在重复累加同一批元素——相邻的两个i之间，其实只差一张牌的进出。顺着这个瓶颈往下想，可以预处理前缀和把每次求和降到 $O(1)$，总复杂度就是 $O(n)$ 了。这是完全正确的做法，但它要同时维护"左边取到哪"和"右边取到哪"两个下标，边界（
i = 0或i = k）容易写错。换个角度做补集转换会更干净：拿走的点数 = 总点数 − 剩下的点数。总点数
total是一个与取法无关的常量，所以「最大化拿走的」完全等价于「最小化剩下的」。而前面已经确认，剩下的一定是长度恰为remain = n - k的连续区间。于是问题彻底变成：在数组里找出长度为remain的连续子数组，使其和最小。这是最标准的定长滑动窗口。状态定义：
windowSum表示以下标right结尾、长度为remain的那个窗口的元素和；minWindow表示已经扫过的所有完整窗口里的最小和。循环不变量是：每轮循环体执行完毕时，若
right ≥ remain - 1，则windowSum恰好等于cardPoints[right - remain + 1 .. right]这remain个元素之和。维持它的方式是每轮先把cardPoints[right]加进来，再在窗口超长时（right ≥ remain）把滑出去的cardPoints[right - remain]减掉，这样窗口长度始终不超过remain，且在right ≥ remain - 1后恰好等于remain。最后答案就是
total - minWindow。remain == 0要单独返回total：此时全部牌都被拿走，根本不存在"中间窗口"这个东西，滑窗循环里的minWindow会保持初值，减出来的结果毫无意义。
解题步骤
- 先把所有点数累加成
total。为什么必须先算总和：整个解法建立在"最大化拿走 = 总和 − 最小化剩下"这个等式上，total是这个等式的锚点。它与任何取法无关，所以只需扫一遍、算一次。- 计算
remain = n - k，若remain == 0立刻返回total。为什么要提前返回：k == n意味着全部拿走、中间不剩任何牌，长度为0的窗口没有定义。若不特判，Java 版的minWindow会停在初值Integer.MAX_VALUE，total - minWindow直接整数下溢成一个巨大的负数。- 用
right从0扫到n - 1，每轮先执行windowSum += cardPoints[right]。为什么先加后减：先把新元素纳入，再判断是否需要吐出旧元素，这样窗口在增长期（前remain - 1轮）能自然地慢慢变长，不需要额外写一段"先填满窗口"的初始化循环。- 当
right >= remain时执行windowSum -= cardPoints[right - remain]。为什么阈值是right >= remain而不是right > remain：加入cardPoints[right]之后窗口里有right + 1个元素（在还没减过任何元素时），只要right + 1 > remain即right >= remain就超长了，必须吐出最左边那个。被吐出的下标是right - remain，因为吐完之后窗口左端应该落在right - remain + 1。- 当
right >= remain - 1时用windowSum更新minWindow。为什么这个条件不能省：right < remain - 1时窗口还没凑满remain个元素，此时的windowSum是一个"半截窗口"的和，必然偏小。全部点数都是正数，这种偏小的值会污染minWindow，让最终答案偏大。right == remain - 1正是第一个完整窗口成型的时刻。- 返回
total - minWindow。为什么不需要再取一次max：所有长度为remain的窗口与所有合法取法是一一对应的，minWindow已经是全体窗口的最小值，减出来自然就是全体取法的最大值。以
cardPoints = [1, 2, 3, 4, 5, 6, 1]、k = 3走一遍（n = 7，total = 22，remain = 4）：
right = 0：windowSum = 1。right < 4不吐出，right < 3窗口未满，不更新。right = 1：windowSum = 3。窗口仍未满。right = 2：windowSum = 6。窗口仍未满（只有3个元素）。right = 3：windowSum = 10，对应窗口[1,2,3,4]。right >= remain - 1首次成立，minWindow = 10。right = 4：先加5得15，因right >= 4吐出cardPoints[0] = 1得14，对应窗口[2,3,4,5]。14 > 10，minWindow保持10。right = 5：加6得20，吐出cardPoints[1] = 2得18，对应窗口[3,4,5,6]。minWindow仍为10。right = 6：加1得19，吐出cardPoints[2] = 3得16，对应窗口[4,5,6,1]。minWindow仍为10。- 循环结束，返回
22 - 10 = 12。验证一下：
minWindow = 10对应保留[1,2,3,4]，也就是右端连拿三张5 + 6 + 1 = 12，确实是最优解——左端拿三张只有1 + 2 + 3 = 6，左二右一是1 + 2 + 1 = 4，左一右二是1 + 6 + 1 = 8，全都不如12。再看漏掉窗口未满判断会怎样：如果去掉
right >= remain - 1这个条件，right = 0时minWindow会被更新成1，最终返回22 - 1 = 21，远超真实上限（拿三张最多也就12），错得离谱。
代码实现
class Solution {
public int maxScore(int[] cardPoints, int k) {
int total = 0;
for (int point : cardPoints) {
total += point;
}
int remain = cardPoints.length - k;
// k == n 时中间不剩牌，长度为 0 的窗口没有定义，必须提前返回。
if (remain == 0) {
return total;
}
int windowSum = 0;
int minWindow = Integer.MAX_VALUE;
for (int right = 0; right < cardPoints.length; right++) {
windowSum += cardPoints[right];
// 窗口元素超过 remain 个就吐出最左边那个，保持定长。
if (right >= remain) {
windowSum -= cardPoints[right - remain];
}
// 只有窗口凑满 remain 个元素后才是合法候选，否则半截窗口会污染最小值。
if (right >= remain - 1) {
minWindow = Math.min(minWindow, windowSum);
}
}
return total - minWindow;
}
}
func maxScore(cardPoints []int, k int) int {
total := 0
for _, point := range cardPoints {
total += point
}
remain := len(cardPoints) - k
// k == n 时中间不剩牌，长度为 0 的窗口没有定义，必须提前返回。
if remain == 0 {
return total
}
windowSum := 0
// remain < n 且点数恒为正，任意窗口和都严格小于 total，用它当初值是安全的。
minWindow := total
for right := 0; right < len(cardPoints); right++ {
windowSum += cardPoints[right]
// 窗口元素超过 remain 个就吐出最左边那个，保持定长。
if right >= remain {
windowSum -= cardPoints[right-remain]
}
// 只有窗口凑满 remain 个元素后才是合法候选，否则半截窗口会污染最小值。
if right >= remain-1 && windowSum < minWindow {
minWindow = windowSum
}
}
return total - minWindow
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：第一个循环求总和扫一遍数组；第二个循环里
right单调递增，每个元素恰好被加入窗口一次、被移出窗口至多一次，循环体内全是常数次加减和比较。两趟线性扫描相加仍是 $O(n)$。- 空间复杂度：$O(1)$。凭什么：只用了
total、remain、windowSum、minWindow、right这几个标量，没有开前缀和数组。这正是滑动窗口相对"预处理前缀和"写法的额外收益——同样是 $O(n)$ 时间，但省掉了 $O(n)$ 的辅助数组。
关键点总结
- 看到"只能从两端操作"就立刻去想补集。两端取走等价于保留中间一段连续区间，这个转换把"两个自由端点"压成"一个定长窗口"，是这一类题的通用钥匙；能不能想到它，基本决定了代码是三十行还是十行。
- 总和恒定时，最大化取走 ≡ 最小化保留。这个等价关系成立的前提是"取走的和保留的构成完整划分"，本题恰好满足。养成先问一句"有没有一个不随选择变化的常量"的习惯，很多最大化问题都能翻成更好写的最小化问题。
- 顺序不影响结果时，绝不要把顺序写进状态。本题左右取牌可以任意穿插，但点数和只与左右各取几张有关，把交替顺序纳入状态会让搜索空间从 $O(k)$ 爆炸到 $O(2^k)$，是新手最常见的过度建模。
- 定长滑窗的三段式模板要背熟：加入右端元素 → 超长则移出左端元素 → 窗口达标才更新答案。三步的先后顺序和各自的判定阈值（
right >= remain与right >= remain - 1差一）是这个模板唯一的技术含量，写完务必用最小规模用例对一遍下标。- 退化情况优先处理。
k == n让窗口长度变成0，它不是"结果恰好正确"的普通边界，而是会让后续逻辑彻底失去意义的非法输入，必须在进入主循环前拦掉。- 面试视角：先说暴力枚举左取几张的 $O(k^2)$，再说前缀和优化到 $O(n)$，最后给出补集 + 定长滑窗的 $O(n)$ 时间 $O(1)$ 空间版本。三层递进能完整展示你的优化路径；如果被追问"为什么保留的一定是连续区间"，用"左前缀 + 右后缀的补集必然连续"一句话回答即可。
易错点总结
- 窗口长度写成
k而不是n - k：cardPoints = [1,2,3,4,5,6,1]、k = 3时会去找长度为3的最小窗口[1,2,3] = 6，返回22 - 6 = 16，而正确答案是12——直接把题目做成了另一道题。- 漏掉
remain == 0的特判：cardPoints = [1,1000,1]、k = 3时 Java 版的minWindow保持Integer.MAX_VALUE，1002 - 2147483647整数下溢，返回一个巨大的正数；正确答案是1002。- 漏掉
right >= remain - 1的窗口达标判断：上面走查过的[1,2,3,4,5,6,1]、k = 3会在right = 0时把minWindow更新成1，返回21，比理论最大值12还大。- 移出元素的下标写成
right - remain + 1：remain = 4且right = 4时会吐出cardPoints[1] = 2而不是cardPoints[0] = 1，窗口内容变成[1,3,4,5]这种不连续的集合，minWindow全程算错。- 判定移出的条件写成
right > remain：remain = 4、right = 4这一轮不会吐出元素，窗口里塞了5个数，此后每个窗口都长一格，[1,2,3,4,5,6,1]、k = 3会返回22 - 15 = 7，低于正确答案12。- Go 里把
minWindow初始化成0：任何窗口和都是正数，windowSum < minWindow永远不成立，minWindow全程保持0，直接返回total = 22，等于宣称能拿走所有牌。- Java 里用
Integer.MAX_VALUE作初值却在循环外忘了保证至少更新一次：只要不特判remain == 0，就会出现"一次都没更新"的情况，随后的减法溢出。初值取极大值和特判退化情况必须成对出现。- 改成枚举左右取牌数却把边界写成
for (i = 1; i < k; i++)：漏掉了"全从右边取"和"全从左边取"两种极端方案，[1,2,3,4,5,6,1]、k = 3里最优解恰好是全从右边取，会被漏掉，答案变成8。- 担心点数和溢出而全程改用
long：n ≤ 10^5、单张点数≤ 10^4，总和上限10^9稳在int范围内，改long不算错但返回值类型是int，多一次强制转换反而容易在收窄时写错。- 试图用双端队列或优先队列来维护"最小窗口"：定长窗口的和是一个滚动更新的标量，直接加减即可 $O(1)$ 维护，引入额外数据结构只会把 $O(1)$ 空间变成 $O(n)$ 且常数更大，面试里会被反问"为什么需要它"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 643. 子数组最大平均数 I | 简单 | 最裸的定长窗口求最大和，没有补集转换这一层，适合先拿它把模板下标校准 |
| 1052. 爱生气的书店老板 | 中等 | 定长窗口求的是"额外收益"而非区间和本身，需要先把基础部分单独累加出来 |
| 1151. 最少交换次数来组合所有的 1 | 中等 | 窗口长度由 1 的总数动态确定，同样用了"最小化窗口内的 0"这种补集视角 |
| 1456. 定长子串中元音的最大数目 | 中等 | 窗口内维护的是计数而非求和，进出元素时需要判定字符类别 |
| 209. 长度最小的子数组 | 中等 | 变长窗口，左边界靠 while 收缩，与本题的定长模板形成对照 |
| 1004. 最大连续1的个数 III | 中等 | 变长窗口 + 容忍度约束，窗口合法性由翻转次数上限而非长度决定 |
| 239. 滑动窗口最大值 | 困难 | 同样是定长窗口，但求最值无法靠加减滚动维护，必须引入单调队列 |