LeetCode 1423 这道 Maximum Points You Can Obtain from Cards（可获得的最大点数），在我的提交记录里耗时稳定在 100ms 附近。第一次看到题目，我以为又是一道“每次从两头挑大的拿”的水题，结果一个反例就让我老老实实坐下来画图。这篇文章我会完整记录一下，我是怎么把“从两端拿卡片”翻译成“找固定长度最小连续子数组”的，为什么贪心不靠谱，以及滑动窗口为什么是这道题最舒服的解法。适合刚接触滑动窗口、还不太会识别题型的读者，也适合刷题时被“两端取数”类题目绕进去的朋友。
1. 题目到底在问什么：一张张从两端拿卡片的取舍问题
1.1 题意与约束条件速览
题目给你一个数组cardPoints，每个元素代表一张卡片的点数。你从数组的最左端或者最右端拿一张卡片，拿走的卡片直接计入得分，总共要拿k张。问最终能拿到的最大点数是多少。
举几个例子。
- 示例 1：
cardPoints = [1,2,3,4,5,6,1]，k = 3。最优策略是先拿右边 1，再拿右边 6，再拿左边 1，得分 1+6+1=8 吗？其实不是，我们也可以先拿左边 1，再拿右边 6，再拿右边 1，得分 8；但这道题示例输出是 12，它是左边拿 1、右边拿 6 和 5？注意只能先拿端点，所以 5 必须等 6 被拿掉后才能拿。目标组合是左边拿 1，右边拿 5、6、1 中的两个？这里最优先：先拿左边 1，再拿右边 6，再拿左边 2？不对，我们直接看结论：最优是拿左边 1、右边 6、右边 5？不行，5 不是端点。手动推一下：n=7，k=3，最后拿到的 3 张牌在原始数组中一定是一段前缀加一段后缀。最优是左边取[1]，右边取[6,1]? 那是 1+6+1=8。 不对，示例输出 12。再想：左边取[1,2]，右边取[6]得分 9。左边取[1]，右边取[5,6]？可不可能？拿牌过程：先拿右边 1，再拿右边 6，再拿右边 5，得分 1+6+5=12。是的，因为每次拿右边端点，连续从右边拿三张，最后拿到的就是原数组最右边三个[4,5,6]？不对，数组中右边是 6,1，没有 5。啊，示例数组是[1,2,3,4,5,6,1]，右边连续三个是[5,6,1]？端点拿三张：先拿 1，再拿 6，再拿 5，得分 12。对，最右三个是 5,6,1，得分 12。所以最优是全右。这恰好说明要枚举左边取几个、右边取几个。 - 示例 2：
cardPoints = [2,2,2]，k = 2，左右各拿一张，得分 4。 - 示例 3：
cardPoints = [9,7,7,9,7,7,9]，k = 3，输出 15。 - 示例 4：
cardPoints = [1,100,1]，k = 1，输出 1，因为只能拿两端的 1 或 1，拿不到 100。
约束条件很关键：1 <= cardPoints[i] <= 10^4，1 <= k <= cardPoints.length。数组长度最大可以到10^5，这意味着任何O(2^k)的暴力枚举都不可能通过。看到这个数据范围，基本就该往“一趟遍历”或“滑动窗口”的方向想。
1.2 贪心直觉为什么是错的
第一次做这道题的人很容易产生一个直觉：既然每次只能从两端拿，那每次比较一下左端和右端谁大，拿大的不就行了？这是典型的贪心想法，可惜它不保证全局最优。
反例很简单：cardPoints = [8, 100, 1, 9]，k = 2。
- 贪心：左端 8，右端 9，先拿 9，数组变成
[8,100,1]，再拿 8，总分 17。 - 最优：拿左端 8，再拿左端 100，总分 108。
为什么贪心错？因为你先拿走某一端后，那一端后面更“肥”的元素才有机会暴露出来。这个决策不是一个独立的端点比较，而是一个“选择左侧连续段还是右侧连续段”的结构性问题。等价地说，你是在决定“从左边拿几个、从右边拿几个”，而不是每一步单独比较端点值的大小。
生活化的类比：排队打饭，你和朋友只能从队伍的两端往里接人，每次只能接队伍最外面的人。队伍开头是两个普通同学，但再往里有几个“大胃王”，而队伍末尾后面全是小胃口。这时候只比较当前最外面的两个人，往往会漏掉藏在里面的高价值目标。
所以看到“只能从两端取”的题，第一反应不要是模拟，而是画一条数组，想想“最后被我拿走的那批元素，在原始数组里会是什么形状”。
1.3 从暴力枚举到可计算模型
既然每一步选左或选右，暴力模拟是2^k种路径。但注意一个关键事实：因为每次都只能从端点取，最终拿走的k张牌，一定是原始数组的左边连续若干个加上右边连续若干个，不可能出现“左侧拿一个，隔一个不拿，再在左侧拿一个”的情况。
这就像你从香蕉的两端剥皮，每个人只能从已经暴露的那端继续往里剥，剥出来的果肉在原始果皮上永远是左边一截加右边一截。
于是我们只需要枚举一个数字：左边拿i张，右边拿k - i张，其中i的取值范围是0到k。如果能在O(k)或O(n)内快速算出每种方案的总分，问题就解决了。
这一段理解是整道题的分水岭。很多题解直接甩出滑动窗口代码，如果你不知道“左连续 + 右连续”这个前提，代码看着就像魔法。
2. 核心思路：把“拿两端”翻过来想
2.1 最终的k张卡片在原始数组里长什么样
先固定一个视角：与其关心“我拿了哪些卡片”，不如关心“我没拿哪些卡片”。
数组长度是n，要拿k张，也就是剩n - k张不被拿走。由于拿走的卡片是左边一段加右边一段，那么没被拿走的卡片自然就是数组正中间的一段连续子数组。注意这段子数组的长度是固定的n - k，并且它在原数组中的位置必须是连续的。
反过来思考：拿走的点数最大，等价于剩下的点数最小。因为整个数组的总点数和是固定的：
拿走的最大值 = 总和 - 剩下部分的最小值
剩下的部分，是一个长度为n - k的连续子数组。于是问题变成了：
在
cardPoints中找到一个长度为n - k的连续子数组，让它的和最小。
这比原题直观多了。原题让你从两端抽牌，每次还要考虑左右顺序，很烧脑；转换后就是一个标准的固定长度滑动窗口求最小值问题。
2.2 等效问题：找长度固定的最小连续子数组
来验证一下这个等价关系。
cardPoints = [1,2,3,4,5,6,1]，n = 7，k = 3，那么n - k = 4。
我们需要在数组中找一个长度为 4 的连续子数组，使其和最小。
[1,2,3,4]和 = 10[2,3,4,5]和 = 14[3,4,5,6]和 = 18[4,5,6,1]和 = 16
最小和是 10，数组总和是 22，所以答案等于 12。这和示例输出完全一致。也就是说，中间留下[1,2,3,4]，两头拿[5,6,1]，得分 12。拿牌过程就是连续从右端拿 1、6、5。
再看反例[8, 100, 1, 9]，n = 4，k = 2，则n - k = 2。
长度为 2 的连续子数组和分别为：
[8,100]和 = 108[100,1]和 = 101[1,9]和 = 10
最小和是 10，总和 118，答案 108。刚才那个 108 的最优方案，正是把中间[1,9]留下，两头拿[8,100]。
到这里你应该能感受到，反向思考的威力在于把“决策问题”变成了“查找问题”。
2.3 为什么滑动窗口能拿到正确答案
固定长度连续子数组的最值问题，最经典的做法就是滑动窗口。窗口长度固定为len = n - k，一开始覆盖数组前len个元素，然后窗口整体向右滑动一格。
滑动的时候，窗口左边的元素离开，右边的元素进入。我们维护一个变量win_sum记录当前窗口内所有元素的和。
窗口从[0, len-1]滑到[1, len]，只需要做两步：
新的窗口和 = 旧窗口和 - cardPoints[left] + cardPoints[right]
其中left是即将离开窗口的元素下标，right是即将进入窗口的元素下标。每次滑动后更新一次最小值，最后用总和减去这个最小值。
这样做的复杂度是O(n)：每个元素被加入窗口一次、移出窗口一次，所有操作都是常数级。空间复杂度O(1)，只用了几个变量。
为什么不是O(k)而是O(n)？因为窗口长度是n - k，窗口从头滑到尾需要遍历整个数组。如果k接近n，窗口长度很小，滑动很快；如果k很小，窗口长度接近n，滑动仍然需要遍历完整个数组。无论哪种情况，O(n)都能轻松跑过n <= 10^5的测试数据。
3. 三种可落地写法与复杂度对比
3.1 前缀和枚举法：最符合直觉的写法
如果你一下想不到反向滑动窗口，用“枚举左边拿几张”的思路也能解。思路是：
- 先算好前缀和数组
prefix，prefix[i]表示前i个元素的和。 - 枚举
left_count从0到k，表示左边拿left_count张，右边拿right_count = k - left_count张。 - 当前方案得分 = 左边
left_count张的和 + 右边right_count张的和。 - 左边和直接用
prefix[left_count]；右边和用总和减去前n - right_count个元素的和。
Python 代码如下：
class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: n = len(cardPoints) prefix = [0] * (n + 1) for i, x in enumerate(cardPoints): prefix[i + 1] = prefix[i] + x total = prefix[n] ans = 0 for left_count in range(k + 1): right_count = k - left_count # 左边前 left_count 个 left_sum = prefix[left_count] # 右边最后 right_count 个 = 总和 - 前 n - right_count 个 right_sum = total - prefix[n - right_count] ans = max(ans, left_sum + right_sum) return ans这个写法有两个容易踩的坑。
第一，left_count必须从0开始，到k结束，不能少掉“全部取右边”和“全部取左边”两种极端情况。
第二，right_count = 0时，n - right_count = n，prefix[n] = total，所以right_sum = 0，逻辑没有问题。prefix数组长度设为n + 1就是为了应对这种取不到右边的情况。
前缀和枚举的时间复杂度是O(n + k)，空间复杂度O(n)。代码很直白，适合在面试中边写边解释。缺点是额外开了一个n+1的数组，在内存限制紧张时不够优雅。
3.2 反向滑动窗口法：最推荐的标准答案
回到我们前面推导出的核心结论：总和固定，剩下中间连续n - k个元素的和最小，拿走的值就最大。
实现的时候，窗口长度我建议用变量名window_len = n - k，不要直接写n-k，不然很容易和“拿k张”搞混。
class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: n = len(cardPoints) total = sum(cardPoints) # 如果 k 等于 n，代表全部拿走，直接返回总和 if k == n: return total window_len = n - k # 先算第一个窗口的和 win_sum = sum(cardPoints[:window_len]) min_win_sum = win_sum # 窗口向右滑动 for right in range(window_len, n): win_sum += cardPoints[right] - cardPoints[right - window_len] if win_sum < min_win_sum: min_win_sum = win_sum return total - min_win_sum解释一下win_sum += cardPoints[right] - cardPoints[right - window_len]这一行。
窗口在滑动前覆盖的是下标[right - window_len, right - 1]，滑动后覆盖的是[right - window_len + 1, right]。新进入窗口的是cardPoints[right]，离开窗口的是窗口最左边的cardPoints[right - window_len]。所以窗口和的变化就是“加新元素、减旧元素”。
C++ 版本同样简洁：
class Solution { public: int maxScore(vector<int>& cardPoints, int k) { int n = cardPoints.size(); int total = accumulate(cardPoints.begin(), cardPoints.end(), 0); if (k == n) return total; int window_len = n - k; int win_sum = accumulate(cardPoints.begin(), cardPoints.begin() + window_len, 0); int min_win_sum = win_sum; for (int i = window_len; i < n; ++i) { win_sum += cardPoints[i] - cardPoints[i - window_len]; min_win_sum = min(min_win_sum, win_sum); } return total - min_win_sum; } };这个版本的优点是时间O(n)、空间O(1)，面试官最喜欢看这种。缺点是需要你先想通“找最小连续子数组”的逆向思维，否则代码容易背错。
3.3 正向双端窗口法：另一种练习思路
既然枚举的是“左边拿几个、右边拿几个”，也可以直接维护一个代表“已拿牌集合”的窗口。先假设全部拿左边的k张，然后逐步把左边牌“吐出来”，换成右边牌。
class Solution: def maxScore(self, cardPoints: List[int], k: int) -> int: n = len(cardPoints) # 全部拿左边 k 张，作为初始方案 cur = sum(cardPoints[:k]) ans = cur # 枚举左边保留的张数 left_count，从 k-1 一直减到 0 for left_count in range(k - 1, -1, -1): # 右边需要拿 right_count 张 right_count = k - left_count # 丢掉当前左边方案中最右边的那张，补上右边新加入的一张 cur += cardPoints[n - right_count] - cardPoints[left_count] ans = max(ans, cur) return ans我还是用[1,2,3,4,5,6,1]，k=3验证一遍。
初始cur = 1+2+3 = 6，方案是左边拿 3 张。
left_count = 2，right_count = 1，cur = 6 + cardPoints[6] - cardPoints[2] = 6 + 1 - 3 = 4，方案是左边 2 张[1,2]，右边 1 张[1]，得分 4。left_count = 1，right_count = 2，cur = 4 + cardPoints[5] - cardPoints[1] = 4 + 6 - 2 = 8，方案是左边[1]，右边[6,1]，得分 8。left_count = 0，right_count = 3，cur = 8 + cardPoints[4] - cardPoints[0] = 8 + 5 - 1 = 12，方案是右边[5,6,1]，得分 12。
这个正向写法的时间复杂度其实是O(k)，因为循环次数是k，初始sum也是O(k)。如果k明显小于n，它比反向滑动窗口更快。但从面试稳定性来看，我更推荐反向滑动窗口，因为下标不容易写晕。正向写法适合作为练习，帮助自己加深对“左连续 + 右连续”的理解。
3.4 复杂度对比表
| 写法 | 核心思路 | 时间复杂度 | 空间复杂度 | 面试推荐度 |
|---|---|---|---|---|
| 暴力 DFS 模拟 | 每一步递归选左或选右 | O(2^k) | O(k) | 不推荐，必超时 |
| 贪心每次取大 | 只看当前端点，局部最优 | O(k) | O(1) | 结果是错的 |
| 前缀和枚举 | 枚举左边拿几张 | O(n + k) | O(n) | 适合先讲思路 |
| 反向滑动窗口 | 求最小连续子数组和 | O(n) | O(1) | 最推荐 |
| 正向双端窗口 | 左边逐步换成右边 | O(k) | O(1) | 适合练习下标控制 |
很多题解只给出反向滑动窗口，但我建议你把前缀和枚举也写一遍。两种方法看似不同，实际上都是在对“左边取几、右边取几”这个枚举做加速。前缀和枚举是“用空间换时间”，滑动窗口是“用数学等价换空间”。
4. 边界条件、易错点与实测细节
4.1 五个最容易写错的地方
第一个，忽略k == n的情况。如果k == n，代表所有卡片都要拿走，答案就是数组总和。如果不单独处理，window_len = 0，滑动窗口长度为 0，代码会进入一个“空窗口”的奇怪状态，虽然有些写法碰巧能算出正确结果，但逻辑上很危险。
第二个，把窗口长度写成k。这是最经典的错误。反向滑动窗口找的是“中间留下没被拿走的连续段”，长度是n - k，不是k。把窗口长度写成k，代码会去计算“拿走的牌里最小连续子数组”，完全偏离题意。
第三个，前缀和求右侧right_sum时下标写错。右边最后right_count个元素的和，应该是total - prefix[n - right_count]，不是prefix[n] - prefix[right_count]。除非你额外维护后缀和数组，否则这里一定要想清楚。
第四个，枚举left_count时漏掉0或k。有些人在for循环里写成range(1, k)，结果漏掉了“全部从右边拿”和“全部从左边拿”这两种极端情况。本题两种极端情况完全可能出现，比如示例 1 的最优解就是全部从右边拿。
第五个，试图真的去模拟“从数组里删掉一个元素”。Python 里pop(0)是 O(n) 的操作，在循环里做会直接超时；用deque虽然两端操作是 O(1)，但依然要枚举所有选法，指数复杂度躲不掉。正确做法永远是先把问题转化成数学表达式，再用滑动窗口或前缀和去算。
4.2 常见问题速查表
| 现象 | 可能原因 | 解决办法 |
|---|---|---|
| 提交超时 | 用 DFS 递归枚举左右选择 | 改成滑动窗口 O(n) |
| 答案偏小 | 窗口长度误写成 k | 改为 window_len = n - k |
| 答案偏大 | 对中间窗口取最大值而不是最小值 | 记录 min_win_sum 而不是 max |
| 结果莫名其妙 | 遗漏 left_count = 0 或 k | 循环范围改成 range(k + 1) |
| k == n 报错 | 空窗口导致代码逻辑异常 | 开头直接 return total |
| 下标越界 | 前缀和数组长度不足 | prefix 开 n+1，多在循环里检查索引 |
补充一个细节：cardPoints[i]最大是10^4，数组长度最大是10^5，所以总和最大是10^9。C++的int范围大约是-2.1e9到2.1e9，算总和不会溢出。但为了更保险，也为了代码可读性，我建议用long或long long来存储总和与窗口和，特别是当你把这道题的思路迁移到更大数据范围时，这一步能帮你省掉一个隐藏 bug。
4.3 实测耗时与优化心态
我在 LeetCode 上跑 Python 版本的提交，耗时大概在 100ms 左右，内存占用约 14MB。这个数据在同类题目里算正常水平。很多人看到别人用 C++ 可以跑出 30ms，就觉得自己代码写法有问题，实际上不是这样。Python 本身的解释执行开销就摆在那里，只要保证算法是 O(n)，100ms 完全足够了。
真正值得优化的不是“从 100ms 压到 80ms”，而是“从 2^k 的超时版本优化到 O(n) 的滑动窗口”。我们要比较的是数量级，不是个位数的毫秒差。
有一次我为了验证滑动窗口逻辑，专门在本地用random生成一个长度为 100000 的随机数组，跑了一遍maxScore，结果不到 0.1 秒。但是同样长度的数组，如果用递归枚举哪怕k只有 30，程序也会卡到怀疑人生。这就是复杂度的意义。
5. 同类题套路与个人刷题建议
5.1 滑动窗口题型的通用模板
做了这道题之后，我最大的收获是终于把滑动窗口的“通用模板”刻进了脑子里。凡是遇到“连续子数组”加“固定长度”或“最大/最小和”这组关键词，都可以往这个框架里套：
- 明确窗口长度，或者明确窗口扩张和收缩的条件。
- 先初始化第一个窗口，算出初始值。
- 用一个变量维护当前窗口的统计值，比如窗口和、窗口最大值、窗口内不同字符数。
- 右边界从窗口右端开始向右移动，每次移动一步。
- 根据题目要求移动左边界，如果是固定长度窗口，左边界也跟着右移；如果是可变长度窗口，用
while收缩左边界。 - 每移动一次，更新答案。
对应到本题：
- 窗口长度固定是
n - k。 - 初始窗口是前
n - k个元素。 - 统计值是窗口和。
- 右边界从
n - k遍历到n - 1，左边界随右边界同步移动。 - 答案记录的是窗口和的最小值，最后一次用总和减掉它。
如果你已经在心里默念这套模板，那么 643 题（Maximum Average Subarray I）、209 题（Minimum Size Subarray Sum）、1004 题（Max Consecutive Ones III）其实都是一回事，只是统计值和窗口调整条件不同。
5.2 卡片类题型的两个方向
“从两端取数”的题目在 LeetCode 里并不少见，但有一个容易混淆的分支。
第一类，就像今天的 1423 题，限制你”总共取 k 次，每次取左端或右端“。这类题的关键是发现：最后取走的一定是左连续段加右连续段，于是枚举分界点即可。如果你愿意再走一步，还能把它转换成“求剩下连续段的最小和”。
第二类，题目允许你左右端交替取多次，甚至关心取到某个特定值的最小操作数，比如 1658 题（Minimum Operations to Reduce X to Zero）。那道题要求你从两端不断移除元素，使得移除的元素和等于x，问最少移除几个。它等价于：在数组中间找一段连续子数组，使子数组和等于total - x，并且这段子数组要尽可能长。剩下的两端自然就是需要移除的部分。思路和 1423 几乎一模一样，只是把“固定长度窗口”换成了“目标和可变长度窗口”。
我建议你把 1423 和 1658 放在同一天刷。先刷 1423 理解“两端拿牌”的本质，再刷 1658 体验“中间连续段”的变体，你会发现第二道题只需要在第一道题的基础上改几行。
5.3 我的一点心得
这道题刷新了我对“逆向思维”的认知。正面看，你每一步都在做选择，像是在玩一个动态规划游戏；反面看，你只关心哪些牌没被拿走，而没被拿走的牌必定是中间连续一段。这一正一反之间，复杂度和思维量都大幅降低。
我个人在实际操作中还有一个习惯：拿到数组类题目，第一件事永远是在草稿纸上画一条横线，用|把左段、中段、右段分隔开。比如cardPoints = [1,2,3,4,5,6,1]，我先画：
[1,2,3,4] | [5,6,1]
中间[1,2,3,4]是“没拿走的”，两段是“要拿走的”。只要把中间段标出来，窗口长度、需要求什么值，全都一目了然。这个方法几乎可以消灭所有下标错误。
最后再分享一个小技巧：如果你的滑动窗口代码跑出了错误答案，不要急着打印整个数组，先用长度为 3 到 5 的简单样例手算一遍，走三四个循环体，错误基本就暴露了。我这道题第一次写反向滑动窗口时，把min_win_sum初始化和窗口更新顺序写反了，结果总是输出总和，就是靠手算[8,100,1,9]这个例子抓出来的。练到最后你会发现，这种“手算小样例”的能力，比记住任何模板都管用。
