【每日一题】可获得的最大点数

文章目录

Tag
题目来源
题目解读
解题思路
- 方法一：滑动窗口
- 方法二：前缀和
写在最后

Tag

【滑动窗口】【前缀和】【数组】【2023-12-03】

题目来源

1423. 可获得的最大点数

题目解读

在一排卡牌中拿出 k 张卡牌，每次必须从这一排卡牌的开头或者末尾进行拿取，返回可以获得卡牌的最大点数。

解题思路

一种解题思路是递归的方法，但是该方法超时了。

每次从开头或者末尾拿取一张卡牌之后，接着从子卡牌中按照同样的方式拿取卡牌，直至拿取 k 次，这是一个典型的子问题，可以使用递归方法来完成。

但是，因为递归的过程实际上是列举了所有的拿取可能，因此时间复杂度为 $\times k)$ ， $N$ 为卡牌数组的长度，根据本题的数据规模，执行规模达到了 $10^10$ ，所以递归方法会超时。

递归超时，另寻他法。

仔细观察拿取方式后，会发现，拿取 k 张卡牌之后，剩下的 n-k 张卡牌是连续的。

那么，问题就转化成了求卡牌数组中长度为 n-k 的连续子数组的最小和。具体实现有两种方法：

滑动窗口；
前缀和。

方法一：滑动窗口

维护一个长度为 n-k 的固定滑窗，在卡牌数组中进行滑动，每次滑动会有一个新的值加入滑窗以及一个旧的值离开滑窗，在滑动中统计最小的连续子数组和。

实现代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        int winSize = n-k;  // 滑窗大小

        // 以前n-k的区间和作为初始值
        int sum = accumulate(cardPoints.begin(), cardPoints.begin() + winSize, 0);
        int minVal = sum;
        for(int i = winSize; i < n; ++i){
            sum += cardPoints[i] - cardPoints[i-winSize];
            minVal = min(minVal, sum);
        }
        return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minVal;
    }
};

复杂度分析

时间复杂度： $O (n)$ ， $n$ 为卡牌数组的长度。

空间复杂度： $O (1)$ 。

方法二：前缀和

维护一个记录数组前缀和的数组 preSum，通过两段前缀和的作差计算连续子数组的和，动态更新最小的连续子数组和。

关于 preSum 的更新，可以参考一文讲清楚【前缀和】。

实现代码

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int n = cardPoints.size();
        vector<int> preSum(n+1);
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i-1] + cardPoints[i-1];
        }

        int winSize = n - k;
        int minSum = 1e9;
        for (int i = 0; i <= k; ++i) {
            minSum = min(minSum, preSum[winSize + i] - preSum[i]);
        }
        return preSum[n] - minSum;
    }
};