壹 ? 引
最近也是浮躁的很，一篇redux的文章写了三千多字才算写了一半...写的泪目了。还是刷刷算法静下心，顺带记录下算法做题过程吧。今天的题来自LeetCode每日打卡，题目出自LeetCode1423. 可获得的最大点数，都说二月是滑动窗口月，最近做的题确实都跟滑动窗口有关....题目描述如下：
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 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
贰 ? 简单的题解
贰 ? 壹 题目分析
先简单解释下题目，给定一个由数字组成的数组，你有k次机会，每次只能从左边或者右边开头取一个数字（注意，取的过程是连续的过程），目的是取k次之后得到的数字综合最大。
我们用图示来解释例子1，这个过程可以理解是上帝视角，因为我们知道怎么选数字和最大：
（黄色为比较过程中的数字，绿色是比较完成已确定的数）
第一次选择，因为只能从左边或者右边往中间选，这两个数字都是1，但是你第二次选择只能紧挨着你上一次选择的数，上帝视角我们很明显得选择最右边的1。
第二次选择，这一次是最左边的1与倒数第二个数字6比较，很明显6更大，我们选择了6。
第三次选择，仍然是最左边的1与倒数第三个数字5比较，很明5更大，于是我们选择了5。
因为k为3，我们得到了最大和的三个数[1,6,5]，和为12。
贰 ? 贰 想法一
我一开始的想法是用双指针，比如l为0，r为数组length-1。这样就表示了最左边与最右边的两个数，然后开始第一次比较，选择更大的数。
如果l更大，那么就让l++，因为数字得紧挨着选择，让l++的数字继续与r比较。如果r更大，自然让r--，继续与l这边的数字比较。
但是，例子一直接否定了我这个想法，比如一开始r和l的两个数字都是1，我们是站在上帝视角知道倒数第二个数更大，所以第一次应该选择最右边的1，但站在程序的角度这就很麻烦了，如果第一次比较两个数字相等，我还得考虑两个数字紧挨着的第二个数谁大谁小，如果这次又相等了？难道继续比较紧挨着的第三个数？那要考虑的就没玩没了了，因此直接否决了这个方案。
贰 ? 叁 想法二
因为k个数字总是连续的，我们假设有个窗口一开始包含了k个数字，它们的和就是最大。比如我们可以假设一开始就是最左边的k个数字的和最大，之后滑动窗口，让窗口不停左滑动（每次滑动一个数字），并比较当前k个数字的和与上次的和谁更大。
我们用图表示这个过程（红框代表这个滑动窗口）：
一开始，我们选中了最左边的k个数字，并求它们的和sum，假设这个和就是最大的。
开始滑动窗口，此时的和应该是减去左边第三个数字并加上最右边第一个数字，这个和和sum比较，看谁更大，记录下来。
继续滑动操作，因为我们一共只能取k个数字，所以滑动过程也只会执行k次。
如果你之前没有思路，看到了这里可以根据此思路自己尝试一下。
下面就是我的实现逻辑：
/**
* @param {number[]} cardPoints
* @param {number} k
* @return {number}
*/
var maxScore = function (cardPoints, k) {
// 想法一：我的想法是双指针，一开始就比较l和r谁大，更大的就缩进，继续比较
// 否定想法一，如果一开始l和r相等，不知道到底缩进谁了
// 想法二：一开始全拿一边的，然后不断减去左边的，加上右边的，看看最大能多大
// 最极端的就是右边k个相加最大，一直把左边k个都减完了
// 先求左边三个的和
let sum = 0;
let ans;
for (let i = 0; i < k; i++) {
sum += cardPoints[i];
};
// 开始执行减去左边的，需要注意的是，左边是从右往左减，右边是从右往左加，按照这个顺序
// 一共需要操作k次
let n = cardPoints.length - 1;
// sum等会要不断减少，会变化，所以要有个比较和大小的参照，我们也假设sum此时就是最大
ans = sum;
while (k > 0) {
sum = sum - cardPoints[k - 1] + cardPoints[n];
// ans用于记录每次计算后更大的那个数字
ans = Math.max(sum, ans);
k--;
n--;
}
return ans;
};
贰 ? 肆 想法三
当然，我看了下还有其它思路，比如我们要求k的和最大，就可以假设length-k个数字的和最小，同样开始滑动找到最小和的组合，那么剩下的k的数字必然和最大（max(k) = sum - min(length-k)）。这里我就直接贴下官方的代码了：
var maxScore = function(cardPoints, k) {
const n = cardPoints.length;
// 滑动窗口大小为 n-k
const windowSize = n - k;
// 选前 n-k 个作为初始值
let sum = 0;
for (let i = 0; i < windowSize; ++i) {
sum += cardPoints[i];
}
let minSum = sum;
for (let i = windowSize; i < n; ++i) {
// 滑动窗口每向右移动一格，增加从右侧进入窗口的元素值，并减少从左侧离开窗口的元素值
sum += cardPoints[i] - cardPoints[i - windowSize];
minSum = Math.min(minSum, sum);
}
let totalSum = 0;
for (let i = 0; i < n; i++) {
totalSum += cardPoints[i];
}
return totalSum - minSum;
};
那么到这里本文结束。