福州企业建站系统,网站开发一般多钱,网站 页面 结构,北京南昌网站建设1423. 可获得的最大点数
几张卡牌 排成一行#xff0c;每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动#xff0c;你可以从行的开头或者末尾拿一张卡牌#xff0c;最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
…1423. 可获得的最大点数
几张卡牌 排成一行每张卡牌都有一个对应的点数。点数由整数数组 cardPoints 给出。
每次行动你可以从行的开头或者末尾拿一张卡牌最终你必须正好拿 k 张卡牌。
你的点数就是你拿到手中的所有卡牌的点数之和。
给你一个整数数组 cardPoints 和整数 k请你返回可以获得的最大点数。
示例 1
输入cardPoints [1,2,3,4,5,6,1], k 3 输出12 解释第一次行动不管拿哪张牌你的点数总是 1 。但是先拿最右边的卡牌将会最大化你的可获得点数。最优策略是拿右边的三张牌最终点数为 1 6 5 12 。 示例 2
输入cardPoints [2,2,2], k 2 输出4 解释无论你拿起哪两张卡牌可获得的点数总是 4 。 示例 3
输入cardPoints [9,7,7,9,7,7,9], k 7 输出55 解释你必须拿起所有卡牌可以获得的点数为所有卡牌的点数之和。 示例 4
输入cardPoints [1,1000,1], k 1 输出1 解释你无法拿到中间那张卡牌所以可以获得的最大点数为 1 。 示例 5
输入cardPoints [1,79,80,1,1,1,200,1], k 3 输出202
提示
1 cardPoints.length 10^5 1 cardPoints[i] 10^4 1 k cardPoints.length
运用逆向思维滑动窗口来解决该题
class Solution {
public:int maxScore(vectorint cardPoints, int k) {int n cardPoints.size();int totalSum 0;for (int i 0; i n; i) {totalSum cardPoints[i];}int windowSize n - k; // 需要找到的子数组的长度int currentSum 0;// 计算第一个窗口的和for (int i 0; i windowSize; i) {currentSum cardPoints[i];}int minSum currentSum;// 滑动窗口找到最小子数组和for (int i windowSize; i n; i) {currentSum cardPoints[i] - cardPoints[i - windowSize];minSum min(minSum, currentSum);}return totalSum - minSum;}};滑动窗口
滑动窗口是一种解决数组/字符串子数组或子串问题的有效方法。它可以在线性时间内解决连续子数组或子串的问题而无需使用额外的数据结构。
在这个问题中我们使用滑动窗口来找到长度为 n-k 的子数组的最小值。这个子数组包含了我们没有选择的卡牌。接下来我们用总和减去这个最小值得到最大点数。
下面是滑动窗口的步骤 计算初始窗口的和 在滑动窗口的初始状态我们计算数组中的前 n-k 个元素的和即第一个窗口的和。这个和被称为当前窗口的和。 滑动窗口 我们从数组的第 n-k 个元素开始向右滑动窗口。在每一步中我们新增一个元素到当前窗口并删除窗口的最左边的元素。这样我们保持窗口的长度为 n-k。 更新最小值 在滑动窗口的过程中我们记录当前窗口的和的最小值。最终我们得到的最小值就是长度为 n-k 的子数组的最小和。 计算最大点数 用总和减去最小子数组的和即为我们可以获得的最大点数。
滑动窗口是通过维护一个可变大小的窗口来处理数组中的子数组问题以提高效率。
