1423. 可获得的最大点数

🎯 问题描述（来源于LeetCode）

描述：
几张卡牌排成一行，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
返回可以获得的最大点数。

说明：

这是一个典型的**“逆向思维 + 滑动窗口”**问题。
从两端取 k 个元素使得和最大，等价于在数组中间保留 n-k 个连续元素使得和最小。
最大得分 = 数组总和 - 中间连续子数组的最小和。
示例：
示例 1：

输入：cardPoints = [1,2,3,4,5,6,1], k = 3
输出：12
解释：
最优策略是从右端取 3 张牌 (1, 6, 5)，和为 12。
逆向思考：数组总和 28。我们要保留 n-k = 4 张牌在中间。
中间连续 4 张牌的最小和是 [4,5,6,1] = 16，则得分 28-16=12。

示例 2：

输入：cardPoints = [9,7,7,9,7,7,9], k = 7
输出：55
解释：
k 等于数组长度，必须拿走所有卡牌。
总和 = 9+7+7+9+7+7+9 = 55。

💻 解题思路

思路1：逆向思维 + 定长滑动窗口

思路1：代码实现

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        # 如果 k 等于数组长度，说明必须拿走所有卡牌，直接返回总和
        # 这避免了后续 m=0 导致的除零或索引错误
        if k == n:
            return sum(cardPoints)
        m = n - k  # m 是中间需要保留的连续子数组长度
        count = 0
        # 初始化最小和为第一个窗口的和（下标 0 到 m-1）
        count_min = sum(cardPoints[:m])
        for i, num in enumerate(cardPoints):
            # 1. 扩展窗口：将当前元素加入总和
            count += num
            # 计算当前窗口的左边界
            left = i - m + 1
            # 2. 窗口未形成：如果左边界小于 0，说明元素不足 m 个，跳过判断
            if left < 0:
                continue
            # 3. 窗口已形成：更新最小和
            count_min = min(count, count_min)
            # 4. 收缩窗口：移除最左边的元素
            count -= cardPoints[left]
        # 结果 = 总和 - 中间连续子数组的最小和
        return sum(cardPoints) - count_min

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是数组 cardPoints 的长度。代码遍历了数组一次。虽然有一行 sum(cardPoints[:m]) 和最后的 sum(cardPoints)，但它们都是线性操作，总体时间复杂度仍为 $O(N)$ 。
空间复杂度： $O(1)$ $O (1)$
- 只使用了常数个额外变量 (n, m, count, count_min, i, left)，没有使用额外的数据结构。

思考

逆向思维转换：
- 直接思考“从两端取”比较困难，因为组合情况多（左0右k, 左1右k-1…）。
- 转换为“中间留”则变成了标准的定长滑动窗口问题：寻找长度为 n-k 的连续子数组，使其和最小。
边界条件修复：
- 之前的代码在 k=n 时会报错 IndexError。
- 原因：当 k=n 时，m = n-k = 0。此时 left = i - 0 + 1 = i + 1。在循环中尝试访问 cardPoints[left] 会导致索引越界（因为 left 会迅速超过数组长度）。
- 修复：添加 if k == n: return sum(cardPoints)，直接处理这种极端情况。
初始化技巧：
- 代码中 count_min = sum(cardPoints[:m]) 预先计算了第一个窗口（即数组最左边 m 个元素）的和。
- 这保证了即使数组中所有数字都很大，count_min 也有一个合理的初始值，而不是 0 或 inf。
滑动窗口逻辑：
- count 始终维护当前遍历到的前缀和。