【LeetCode】可获得的最大点数

HQ数字卡

关注

发布于: 2021 年 02 月 06 日

2021 年 2 月 6 日 LeetCode 的每日一题，依旧是滑动窗口的应用。

题目

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

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

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

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

代码

public class DayCode {    public static void main(String[] args) {        int[] cardPoints = new int[]{1,2,3,4,5,6,1};        int k = 3;        int ans = new DayCode().maxScore(cardPoints, k);        System.out.println("ans is " + ans);    }
    /**     * https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/     * @param cardPoints     * @param k     * @return     */    public int maxScore(int[] cardPoints, int k) {        int n = cardPoints.length;        int windowSize = n - k;        int sum = 0;        for (int i = 0; i < windowSize; i++) {            sum += cardPoints[i];        }        int minSum = sum;        for (int i = windowSize; i < n; i++) {            sum += cardPoints[i] - cardPoints[i - windowSize];            minSum = Math.min(minSum, sum);        }        return Arrays.stream(cardPoints).sum() - minSum;    }}

复制代码

总结

今天第一次写这个题目的时候，首先想到的是贪心，每次取最大值然后求和，5 行代码搞定，心中还有一丝想法，为什么不是滑动窗口？果然，提交之后，有测试用例报错。
翻看题解之后，再次阅读题目，由于只能从开头和结尾拿掉总共 k 张牌，因此剩下的牌必然连续，就转化成为求 n - k 滑动窗口的和的最小值。
以上代码时间复杂度 O(n),空间复杂度 O(1)

发布于: 2021 年 02 月 06 日阅读数: 13

原文链接:【http://xie.infoq.cn/article/ce081c8fd5036c7e955b958be】。文章转载请联系作者。

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

发布

暂无评论

创作场景

【LeetCode】可获得的最大点数

题目

代码

总结

HQ数字卡

评论