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
解释：你必须拿所有卡牌，可以获得的点数为所有卡牌的点数之和。

提示：

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

解题思路

这道题有两种主要思路：

方法一：前缀和枚举（推荐） 我们可以枚举从左边取 i 张牌，从右边取 k-i 张牌的所有情况。使用前缀和预处理，快速计算任意区间的和。时间复杂度 O(k)，空间复杂度 O(k)。

方法二：滑动窗口 换个角度思考：要取 k 张牌获得最大点数，等价于剩余 n-k 张连续的牌点数和最小。我们可以用滑动窗口找到长度为 n-k 的子数组的最小和，然后用总和减去这个最小和即为答案。

两种方法的时间复杂度都是 O(n)，但方法一的常数因子更小，实现也更直观。当 k 较小时，方法一的实际复杂度接近 O(k)，更加高效。

核心思想是：由于只能从两端取牌，最优解必然是"从左边取 i 张，从右边取 k-i 张"的某种组合。我们枚举所有可能的 i 值，计算对应的点数和，取最大值即可。

代码实现

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        
        // 计算从左边取 i 张牌的前缀和
        vector<int> leftSum(k + 1, 0);
        for (int i = 0; i < k; i++) {
            leftSum[i + 1] = leftSum[i] + cardPoints[i];
        }
        
        // 计算从右边取 j 张牌的前缀和
        vector<int> rightSum(k + 1, 0);
        for (int i = 0; i < k; i++) {
            rightSum[i + 1] = rightSum[i] + cardPoints[n - 1 - i];
        }
        
        int maxPoints = 0;
        // 枚举从左边取 i 张，从右边取 k-i 张
        for (int i = 0; i <= k; i++) {
            maxPoints = max(maxPoints, leftSum[i] + rightSum[k - i]);
        }
        
        return maxPoints;
    }
};

class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        
        # 计算从左边取 i 张牌的前缀和
        left_sum = [0] * (k + 1)
        for i in range(k):
            left_sum[i + 1] = left_sum[i] + cardPoints[i]
        
        # 计算从右边取 j 张牌的前缀和
        right_sum = [0] * (k + 1)
        for i in range(k):
            right_sum[i + 1] = right_sum[i] + cardPoints[n - 1 - i]
        
        max_points = 0
        # 枚举从左边取 i 张，从右边取 k-i 张
        for i in range(k + 1):
            max_points = max(max_points, left_sum[i] + right_sum[k - i])
        
        return max_points

public class Solution {
    public int MaxScore(int[] cardPoints, int k) {
        int n = cardPoints.Length;
        
        // 计算从左边取 i 张牌的前缀和
        int[] leftSum = new int[k + 1];
        for (int i = 0; i < k; i++) {
            leftSum[i + 1] = leftSum[i] + cardPoints[i];
        }
        
        // 计算从右边取 j 张牌的前缀和
        int[] rightSum = new int[k + 1];
        for (int i = 0; i < k; i++) {
            rightSum[i + 1] = rightSum[i] + cardPoints[n - 1 - i];
        }
        
        int maxPoints = 0;
        // 枚举从左边取 i 张，从右边取 k-i 张
        for (int i = 0; i <= k; i++) {
            maxPoints = Math.Max(maxPoints, leftSum[i] + rightSum[k - i]);
        }
        
        return maxPoints;
    }
}

/**
 * @param {number[]} cardPoints
 * @param {number} k
 * @return {number}
 */
var maxScore = function(cardPoints, k) {
    const n = cardPoints.length;
    
    // 计算从左边取 i 张牌的前缀和
    const leftSum = new Array(k + 1).fill(0);
    for (let i = 0; i < k; i++) {
        leftSum[i + 1] = leftSum[i] + cardPoints[i];
    }
    
    // 计算从右边取 j 张牌的前缀和
    const rightSum = new Array(k + 1).fill(0);
    for (let i = 0; i < k; i++) {
        rightSum[i + 1] = rightSum[i] + cardPoints[n - 1 - i];
    }
    
    let maxPoints = 0;
    // 枚举从左边取 i 张，从右边取 k-i 张
    for (let i = 0; i <= k; i++) {
        maxPoints = Math.max(maxPoints, leftSum[i] + rightSum[k - i]);
    }
    
    return maxPoints;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(k)需要计算两个长度为k的前缀和，然后枚举k+1种情况
空间复杂度O(k)需要两个长度为k+1的数组存储前缀和

相关题目