1423. 可获得的最大点数

1423. 可获得的最大点数 #

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

题目大意 #

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

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

现在给定一个整数数组 cardPoints 和整数 k

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

解题思路 #

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

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

  1. window_sum 用来维护窗口内的元素和,初始值为 0min_sum 用来维护滑动窗口元素的最小和。初始值为 sum(cardPoints)。滑动窗口的长度为 window_size,值为 len(cardPoints) - k
  2. 使用双指针 leftrightleftright 都指向序列的第一个元素,即:left = 0right = 0
  3. 向右移动 right,先将 window_size 个元素填入窗口中。
  4. 当窗口元素个数为 window_size 时,即:right - left + 1 >= window_size 时,计算窗口内的元素和,并维护子数组最小和 min_sum
  5. 然后向右移动 left,从而缩小窗口长度,即 left += 1,使得窗口大小始终保持为 k
  6. 重复 4 ~ 5 步,直到 right 到达数组末尾。
  7. 最后输出 sum(cardPoints) - min_sum 即为答案。

注意:如果 window_size0 时需要特殊判断,此时答案为数组和 sum(cardPoints)

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
本站总访问量  次  |  您是本站第  位访问者