1423. Maximum Points You Can Obtain from Cards

Leetcode link

解题思路

本题给定我们一个数组，要求我们每次只能从数组两端取值，要求取 k 次之后总和最大

这个题目其实很适合用滑动窗口来求解，有两种思路：

• 假想数组头尾拼接起来，从数组最后 k 个开始遍历，然后遍历最后 k-1 个到第一个，最后 k-2 个到第二个。。。
• 求数组剩余连续部分的最小值，然后用数组总和减去最小值，因为剩余部分最小表示取的 k 个最大

C++

class Solution {
public:
    int maxScore(vector<int>& cardPoints, int k) {
        int total = accumulate(cardPoints.begin(), cardPoints.end(), 0);
        int len = cardPoints.size();

        int windowSize = len - k;
        int left = 0, right = windowSize - 1;
        int sum = accumulate(cardPoints.begin(), cardPoints.begin() + windowSize, 0);
        int minSum = sum;

        while(right < len - 1) {
            sum -= cardPoints[left++];
            sum += cardPoints[++right];
            minSum = min(minSum, sum);
        }

        return total - minSum;
    }
};

Javascript

/**
 * @param {number[]} cardPoints
 * @param {number} k
 * @return {number}
 */
var maxScore = function(cardPoints, k) {
    let totalSum = cardPoints.reduce((prev, cur)=> prev + cur, 0);
    let len = cardPoints.length;
    // window size
    let size = len - k;
    let left = 0, right = size - 1;
    let sum = 0;
    for(let i=0;i<size;i++) {
        sum+=cardPoints[i];
    }
    let min = sum;

    while(right < len - 1) {
        sum-=cardPoints[left++];
        sum+=cardPoints[++right];
        min = Math.min(min, sum);
    }
    return totalSum - min;
};