1423-可获得的最大点数(Maximum Points You Can Obtain from Cards)

原文链接: https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards

英文原文

There are several cards arranged in a row, and each card has an associated number of points. The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1.

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

1 <= cardPoints.length <= 10⁵
1 <= cardPoints[i] <= 10⁴
1 <= k <= cardPoints.length

中文题目

几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 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

通过代码

高赞题解

方法一：滑动窗口

思路

记数组 $\textit{cardPoints}$ 的长度为 $n$，由于只能从开头和末尾拿 $k$ 张卡牌，所以最后剩下的必然是连续的 $n-k$ 张卡牌。

我们可以通过求出剩余卡牌点数之和的最小值，来求出拿走卡牌点数之和的最大值。

算法

由于剩余卡牌是连续的，使用一个固定长度为 $n-k$ 的滑动窗口对数组 $\textit{cardPoints}$ 进行遍历，求出滑动窗口最小值，然后用所有卡牌的点数之和减去该最小值，即得到了拿走卡牌点数之和的最大值。

代码

[sol1-C++]
class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        // 滑动窗口大小为 n-k
        int windowSize = n - k;
        // 选前 n-k 个作为初始值
        int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
        int minSum = sum;
        for (int i = windowSize; i < n; ++i) {
            // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
            sum += cardPoints[i] - cardPoints[i - windowSize];
            minSum = min(minSum, sum);
        }
        return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minSum;
    }
};

[sol1-Python3]
class Solution:
    def maxScore(self, cardPoints: List[int], k: int) -> int:
        n = len(cardPoints)
        # 滑动窗口大小为 n-k
        windowSize = n - k
        # 选前 n-k 个作为初始值
        s = sum(cardPoints[:windowSize])
        minSum = s
        for i in range(windowSize, n):
            # 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
            s += cardPoints[i] - cardPoints[i - windowSize]
            minSum = min(minSum, s)
        return sum(cardPoints) - minSum

[sol1-Java]
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int n = cardPoints.length;
        // 滑动窗口大小为 n-k
        int windowSize = n - k;
        // 选前 n-k 个作为初始值
        int sum = 0;
        for (int i = 0; i < windowSize; ++i) {
            sum += cardPoints[i];
        }
        int minSum = sum;
        for (int i = windowSize; i < n; ++i) {
            // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
            sum += cardPoints[i] - cardPoints[i - windowSize];
            minSum = Math.min(minSum, sum);
        }
        return Arrays.stream(cardPoints).sum() - minSum;
    }
}

[sol1-Golang]
func maxScore(cardPoints []int, k int) int {
    n := len(cardPoints)
    // 滑动窗口大小为 n-k
    windowSize := n - k
    // 选前 n-k 个作为初始值
    sum := 0
    for _, pt := range cardPoints[:windowSize] {
        sum += pt
    }
    minSum := sum
    for i := windowSize; i < n; i++ {
        // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
        sum += cardPoints[i] - cardPoints[i-windowSize]
        minSum = min(minSum, sum)
    }
    total := 0
    for _, pt := range cardPoints {
        total += pt
    }
    return total - minSum
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

[sol1-JavaScript]
var maxScore = function(cardPoints, k) {
    const n = cardPoints.length;
    // 滑动窗口大小为 n-k
    const windowSize = n - k;
    // 选前 n-k 个作为初始值
    let sum = 0;
    for (let i = 0; i < windowSize; ++i) {
        sum += cardPoints[i];
    }
    let minSum = sum;
    for (let i = windowSize; i < n; ++i) {
        // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
        sum += cardPoints[i] - cardPoints[i - windowSize];
        minSum = Math.min(minSum, sum);
    }
    let totalSum = 0;
    for (let i = 0; i < n; i++) {
        totalSum += cardPoints[i];
    }
    return totalSum - minSum;
};

[sol1-C]
int maxScore(int* cardPoints, int cardPointsSize, int k) {
    int n = cardPointsSize;
    // 滑动窗口大小为 n-k
    int windowSize = n - k;
    // 选前 n-k 个作为初始值
    int sum = 0;
    for (int i = 0; i < windowSize; i++) {
        sum += cardPoints[i];
    }
    int ret = sum;
    int minSum = sum;
    for (int i = windowSize; i < n; ++i) {
        // 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
        sum += cardPoints[i] - cardPoints[i - windowSize];
        minSum = fmin(minSum, sum);
        ret += cardPoints[i];
    }
    return ret - minSum;
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是数组 $\textit{cardPoints}$ 的长度。
空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
36067	65103	55.4%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

凤起丶宛南

从来没有真正的绝境，只有心灵的迷途