1423. 可获得的最大点数
一、题目
几张卡牌 排成一行,每张卡牌都有一个对应的点数。点数由整数数组 cardPoints
给出。
每次行动,你可以从行的开头或者末尾拿一张卡牌,最终你必须正好拿 k
张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints
和整数 k
,请你返回可以获得的最大点数。
示例1:
1 | 输入:cardPoints = [1,2,3,4,5,6,1], k = 3 |
示例2:
1 | 输入:cardPoints = [2,2,2], k = 2 |
示例3:
1 | 输入:cardPoints = [9,7,7,9,7,7,9], k = 7 |
示例4:
1 | 输入:cardPoints = [1,1000,1], k = 1 |
示例5:
1 | 输入:cardPoints = [1,79,80,1,1,1,200,1], k = 3 |
提示:
- $1 ≤ cardPoints.length ≤ 10^{5}$
- $1 ≤ cardPoints[i] ≤ 10^{4}$
- $1 ≤ k ≤ cardPoints.length$
二、题解
滑动窗口
思路如下:
题目限制我们只能从开头或结尾拿数字,那么最后剩下的数字一定是连续的
这样我们可以换一种思维,我们找到连续数字和最小的这个滑动窗口即可
滑动窗口的长度:
- 时间复杂度:$O(n)$,其中 $n$ 是数组 $cardPoints$ 的长度。
- 空间复杂度:$O(1)$
1 | var maxScore = function (cardPoints, k) { |