LeetCode 题解工作台
可获得的最大点数
几张卡牌 排成一行 ，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。 每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。 你的点数就是你拿到手中的所有卡牌的点数之和。 给你一个整数数组 cardPoints 和整数 k ，请你返回可以获得的最大点数…
3
题型
14
代码语言
3
相关题
当前训练重点
中等 · 滑动窗口（状态滚动更新）
答案摘要
我们可以用一个长度为 的滑动窗口来模拟这个过程。 初始时我们将窗口放在数组的末尾，即索引为 到索引 的这 个位置，窗口内卡牌的点数之和记为 ，初始答案 的值也为 。这其实是从数组的开头拿走 张卡牌的情况。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 滑动窗口（状态滚动更新） 题型思路
题目描述
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。
示例 1：
输入：cardPoints = [1,2,3,4,5,6,1], k = 3 输出：12 解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。
示例 2：
输入：cardPoints = [2,2,2], k = 2 输出：4 解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。
示例 3：
输入：cardPoints = [9,7,7,9,7,7,9], k = 7 输出：55 解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。
示例 4：
输入：cardPoints = [1,1000,1], k = 1 输出：1 解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。
示例 5：
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3 输出：202
提示：
1 <= cardPoints.length <= 10^51 <= cardPoints[i] <= 10^41 <= k <= cardPoints.length
解题思路
方法一：滑动窗口
我们可以用一个长度为 的滑动窗口来模拟这个过程。
初始时我们将窗口放在数组的末尾，即索引为 到索引 的这 个位置，窗口内卡牌的点数之和记为 ，初始答案 的值也为 。这其实是从数组的开头拿走 张卡牌的情况。
接下来，我们考虑从数组的开头依次拿 张卡牌的情况，假设取到的卡牌为 ，那么我们将其加入 ，由于窗口的长度限制为 ，我们需要将 从 中减去，这样我们就可以计算出拿到的 张卡牌的点数之和，更新答案 。
时间复杂度 ，其中 给题目中给出的整数。空间复杂度 。
class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
ans = s = sum(cardPoints[-k:])
for i, x in enumerate(cardPoints[:k]):
s += x - cardPoints[-k + i]
ans = max(ans, s)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate understands sliding window technique and its applications in array-based problems.
- question_mark
Candidate is able to optimize the sum calculation using prefix sums.
- question_mark
Candidate shows awareness of both time and space complexities in their approach.
常见陷阱
外企场景- error
Failing to properly calculate the sum of the remaining cards after removing a subarray.
- error
Overlooking the need to use a sliding window of the correct size (n - k) for optimal performance.
- error
Not handling edge cases where the array length is small or where k equals the length of the array.
进阶变体
外企场景- arrow_right_alt
Solve for the case where k is equal to the length of the array.
- arrow_right_alt
Explore alternate approaches using dynamic programming to solve the problem.
- arrow_right_alt
Find a way to optimize the solution for extremely large arrays (n approaching 100,000).