可获得的最大点数

标签: 数组 前缀和 滑动窗口

难度: Medium

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 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^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

Submission

运行时间: 44 ms

内存: 26.0 MB

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        width = n - k  # 滑动窗口宽度
        cardPointSum = 0
        for x in cardPoints:
            cardPointSum += x
        s = sum(cardPoints[:width]) # 滑动窗口大小
        minSum = s  # 最小滑动窗口
        for i in range(width,n):
            s += cardPoints[i] - cardPoints[i-width]
            if s < minSum:
                minSum = s
        return cardPointSum - minSum

Explain

这个题解采用了滑动窗口的方法来优化求解过程。首先计算卡牌总点数。然后，由于我们要从卡牌序列的两端取出共计 k 张卡牌，可以等效地看作从中间留下长度为 n-k 的连续卡牌子序列，使得这个子序列的点数最小，从而使得取出的 k 张卡牌的点数最大。具体实现中，首先计算了整个卡牌的点数总和，然后通过滑动窗口计算所有可能的长度为 n-k 的子序列的点数和，并找出这些和中的最小值。最后，用总点数减去这个最小的子序列和，就得到了能够从两端取 k 张卡牌得到的最大点数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        width = n - k  # 滑动窗口的宽度, 等于n-k
        cardPointSum = sum(cardPoints)  # 计算所有卡牌的总点数
        s = sum(cardPoints[:width]) # 初始化滑动窗口的和
        minSum = s  # 设初始的最小和为窗口的和
        for i in range(width, n):
            s += cardPoints[i] - cardPoints[i-width]  # 移动窗口，加入新元素，移除旧元素
            if s < minSum:
                minSum = s  # 更新最小和
        return cardPointSum - minSum  # 最大点数为总点数减去最小窗口和

Explore

这个问题的关键在于，我们需要从卡牌的两端选择卡牌以最大化得分，这等价于在卡牌序列中留下一个最小点数的连续子序列。如果我们尝试直接从两端寻找最大点数组合，将涉及到极大的组合可能性，这会导致时间复杂度过高，尤其是当 k 的值较大时。滑动窗口方法可以有效地在 O(n) 时间内找到这个最小的连续子序列，因为通过逐步移动窗口，我们可以在不重复计算的情况下，快速更新窗口内的点数总和。

在题目中，我们的目标是从卡牌的两端取出总共 k 张卡牌，这意味着留在卡牌序列中的卡牌数量为 n-k。为了使从两端取出的卡牌点数最大，我们需要使留在序列中的这部分卡牌的点数总和最小。因此，滑动窗口的宽度应该被设定为 n-k，这样窗口覆盖的就是留在序列中的卡牌，我们通过寻找这个宽度的窗口中的最小点数和来达到目的。

在初始化滑动窗口时，从索引0开始的 width 个元素作为起始点是出于简化实现的考虑。这样可以从序列的开始处逐步向右滑动窗口，直到窗口到达序列的末端。这种方法保证了每个可能的窗口位置都被考虑到，同时简化了逻辑，因为我们无需考虑窗口的初始位置。从任意位置开始并不会提供额外的优势，且会使实现复杂化。

该算法在更新滑动窗口的最小和时使用简单的比较和赋值操作是有效的，因为我们的目标是找到所有可能的窗口和中的最小值。在窗口逐步滑动过程中，我们对每个新的窗口和进行计算，并与当前记录的最小和进行比较。如果新的窗口和更小，则更新最小和。这种方法是有效的，因为它保证了在滑动窗口覆盖整个序列的过程中，每次计算后我们都有当前最小的连续子序列和。这一点在所有情况下都保持有效，无需复杂的数据结构或额外的逻辑。