巧妙的滑动窗口 -- leetcode1423

题干#

1423. 可获得的最大点数

几张卡牌** 排成一行**，每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。

每次行动，你可以从行的开头或者末尾拿一张卡牌，最终你必须正好拿 k 张卡牌。

你的点数就是你拿到手中的所有卡牌的点数之和。

给你一个整数数组 cardPoints 和整数 k，请你返回可以获得的最大点数。

示例 1：

1
输入：cardPoints = [1,2,3,4,5,6,1], k = 3
2
输出：12
3
解释：第一次行动，不管拿哪张牌，你的点数总是 1 。但是，先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌，最终点数为 1 + 6 + 5 = 12 。

示例 2：

1
输入：cardPoints = [2,2,2], k = 2
2
输出：4
3
解释：无论你拿起哪两张卡牌，可获得的点数总是 4 。

示例 3：

1
输入：cardPoints = [9,7,7,9,7,7,9], k = 7
2
输出：55
3
解释：你必须拿起所有卡牌，可以获得的点数为所有卡牌的点数之和。

示例 4：

1
输入：cardPoints = [1,1000,1], k = 1
2
输出：1
3
解释：你无法拿到中间那张卡牌，所以可以获得的最大点数为 1 。

示例 5：

1
输入：cardPoints = [1,79,80,1,1,1,200,1], k = 3
2
输出：202

提示：

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

解题思路#

依照题意，只能从头尾拿牌，因此剩余的牌一定为连续（重点）由此联想到滑动窗口

且求出可拿牌的最大和，因此剩下的牌一定总和最小

问题转换为：求和最小的定长为 n - k的滑动窗口

代码#

1
class Solution {
2
    public:
3
        int maxScore(vector<int>& cardPoints, int k) {
4
            int n = cardPoints.size();
5
            int sum = 0;
6
            if(n == k) return accumulate(cardPoints.begin(), cardPoints.end(), 0);
7
            for(int i = 0;i < n - k;i++){
8
                sum += cardPoints[i];
9
            }
10
            int minSum = sum;
11
            for(int i = n - k;i < n;i++){
12
                sum += cardPoints[i] - cardPoints[i - n + k];
13
                minSum = min(minSum, sum);
14
        }
15
        return accumulate(cardPoints.begin(), cardPoints.end(), 0) - minSum;
16
    }
17
};

原文发布于 CSDN：巧妙的滑动窗口 — leetcode1423