跳至主要內容

1423. 可获得的最大点数

ITCharge大约 3 分钟

1423. 可获得的最大点数open in new window

  • 标签:数组、前缀和、滑动窗口
  • 难度:中等

题目链接

题目大意

描述:将卡牌排成一行,给定每张卡片的点数数组 cardPointscardPoints,其中 cardPoints[i]cardPoints[i] 表示第 ii 张卡牌对应点数。

每次行动,可以从行的开头或者末尾拿一张卡牌,最终保证正好拿到了 kk 张卡牌。所得点数就是你拿到手中的所有卡牌的点数之和。

现在给定一个整数数组 cardPointscardPoints 和整数 kk

要求:返回可以获得的最大点数。

说明

  • 1cardPoints.length1051 \le cardPoints.length \le 10^5
  • 1cardPoints[i]1041 \le cardPoints[i] \le 10^4
  • 1kcardPoints.length1 \le k \le cardPoints.length

示例

  • 示例 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

解题思路

思路 1:滑动窗口

可以用固定长度的滑动窗口来做。

由于只能从开头或末尾位置拿 kk 张牌,则最后剩下的肯定是连续的 len(cardPoints)klen(cardPoints) - k 张牌。要求求出 kk 张牌可以获得的最大收益,我们可以反向先求出连续 len(cardPoints)klen(cardPoints) - k 张牌的最小点数。则答案为 sum(cardPoints)minsumsum(cardPoints) - min\underline{}sum。维护一个固定长度为 len(cardPoints)klen(cardPoints) - k 的滑动窗口,求最小和。具体做法如下:

  1. windowsumwindow\underline{}sum 用来维护窗口内的元素和,初始值为 00minsummin\underline{}sum 用来维护滑动窗口元素的最小和。初始值为 sum(cardPoints)sum(cardPoints)。滑动窗口的长度为 windowsizewindow\underline{}size,值为 len(cardPoints)klen(cardPoints) - k
  2. 使用双指针 leftleftrightrightleftleftrightright 都指向序列的第一个元素,即:left = 0right = 0
  3. 向右移动 rightright,先将 windowsizewindow\underline{}size 个元素填入窗口中。
  4. 当窗口元素个数为 windowsizewindow\underline{}size 时,即:rightleft+1windowsizeright - left + 1 \ge window\underline{}size 时,计算窗口内的元素和,并维护子数组最小和 minsummin\underline{}sum
  5. 然后向右移动 leftleft,从而缩小窗口长度,即 left += 1,使得窗口大小始终保持为 kk
  6. 重复 4 ~ 5 步,直到 rightright 到达数组末尾。
  7. 最后输出 sum(cardPoints)minsumsum(cardPoints) - min\underline{}sum 即为答案。

注意:如果 windowsizewindow\underline{}size00 时需要特殊判断,此时答案为数组和 sum(cardPoints)sum(cardPoints)

思路 1:代码

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        window_size = len(cardPoints) - k
        window_sum = 0
        cards_sum = sum(cardPoints)
        min_sum = cards_sum

        left, right = 0, 0
        if window_size == 0:
            return cards_sum

        while right < len(cardPoints):
            window_sum += cardPoints[right]

            if right - left + 1 >= window_size:
                min_sum = min(window_sum, min_sum)
                window_sum -= cardPoints[left]
                left += 1

            right += 1

        return cards_sum - min_sum

思路 1:复杂度分析

  • 时间复杂度O(n)O(n),其中 nn 为数组 cardPointscardPoints 中的元素数量。
  • 空间复杂度O(1)O(1)