可获得的最大点数

发表于
本文字数： 901 阅读时长 ≈ 1 分钟

LeetCode每日一题，1423. Maximum Points You Can Obtain From Cards

先看题目描述

yYyUKO.png

大意就是给定一个数组 cardPoints 代表牌的点数，我们每次只能取出第一张牌或最后一张牌，一共能取 k 次，问可获得的最大点数是多少

算法和思路

滑动窗口

由于每次只能取起始或末尾的牌，一共能取 k 次，因此取出的牌一定是连续的 k 张牌，且必然包含第一张牌或最后一张牌。于是只需要先构建一个以第一张牌为起点的长度为 k 的滑动窗口，然后将其逆向滑动 k 次，滑动过程中维护可获得点数的最大值，最后将最大点数返回即可

算法源码

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int maxScore(int[] cardPoints, int k) {
        int len = cardPoints.length;
        int cur = 0;
        int left = len - 1;
        int right = k - 1;
        for (int i = 0; i < k; i++) {
            cur += cardPoints[i];
        }
        if (len == k) {
            return cur;
        }
        int max = cur;
        for (int i = 0; i < k; i++) {
            cur -= cardPoints[right];
            right--;
            cur += cardPoints[left];
            left--;
            max = Math.max(cur, max);
        }
        return max;
    }
}