【LeetCode】1423. 可获得的最大点数

发表于 更新于 分类于 Valine：
本文字数： 312 阅读时长 ≈ 1 分钟

1423. 可获得的最大点数

思路

滑动窗口

逆向思维，记数组 $cardPoints$ 的长度为 $n$，由于只能从开头和末尾拿 $k$ 张卡牌，所以最后剩下的必然是连续的 $n-k$ 张卡牌。
我们可以通过求出剩余卡牌点数之和的最小值，来求出拿走卡牌点数之和的最大值。

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

拓展

  1. accumulate函数
    int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);

代码

滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
    }
};