本文关键词：LeetCode，力扣，算法，算法题，滑动窗口，递归，前缀和，preSum，刷题群
题目地址：https://leetcode-cn.com/problems/maximum-points-you-can-obtain-from-cards/
题目描述
几张卡牌 排成一行，每张卡牌都有一个对应的点数。点数由整数数组 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
解题思路
递归
你是不是跟我一样，拿到今天题目的第一想法是模拟题目取卡牌的过程呢？模拟的方法可以用递归。但是递归的过程是把所有的可能组合方式都求了一遍，时间复杂度会达到 O(N*k) ，在题目所给出的 10 ^ 5 的数据规模下，会超时。
下面的代码是我用的递归+记忆化的方式写的，虽然有记忆化，但是因为没有降低时间复杂度，所以仍然超时。提供在这里仅供大家参考。欢迎大家提供能 AC 的递归方法。
我定义的递归函数 dfs(cardPoints, i, j, k) ，表示在 cardPoints 的第 i ~ j 的位置中（包含i,j），从两端抽取 k 个卡牌能够获得的最大点数。那么当 k == 0 的时候，说明不抽牌，结果是 0。当 k != 0 的时候，抽取 k 个卡牌能拿到的点数等于 max(抽取最左边卡牌的点数 + 剩余卡牌继续抽获得的最大点数, 抽取最右边卡牌的点数 + 剩余卡牌继续抽获得最大点数)。
时间复杂度是 O(N ^ 2) 。
class Solution(object):
def maxScore(self, cardPoints, k):
"""
:type cardPoints: List[int]
:type k: int
:rtype: int
"""
N = len(cardPoints)
self.memo = {}
return self.dfs(cardPoints, 0, N - 1, k)
def dfs(self, cardPoints, i, j, k):
if k == 0:
return 0
if (i, j) in self.memo:
return self.memo[(i, j)]
removeLeft = cardPoints[i] + self.dfs(cardPoints, i + 1, j, k - 1)
removeRight = cardPoints[j] + self.dfs(cardPoints, i, j - 1, k - 1)
res = max(removeLeft, removeRight)
self.memo[(i, j)] = res
return res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
preSum
当数据规模到达了 10 ^ 5 ，已经在提醒我们这个题应该使用 O(N) 的解法。
把今天的这个问题思路整理一下，题目等价于：求从 cardPoints 最左边抽 i 个数字，从 cardPoints 最右边抽取 k - i 个数字，能抽取获得的最大点数是多少。
一旦这么想，立马柳暗花明：抽走的卡牌点数之和 = cardPoints 所有元素之和 - 剩余的中间部分元素之和。
我们同样使用模拟法，但是比递归方法高妙的地方在，我们一次性从左边抽走 i 个数字： i 从 0 到 k 的遍历，表示从左边抽取了的元素数，那么从右边抽取的元素数是 k - i 个。现在问题是怎么快速求 剩余的中间部分元素之和？
没错，preSum！我的题解中已经多次分享过 preSum 的思想，下面是 preSum 的介绍，已经看过我前几天题解的朋友可以直接跳过。
求区间的和可以用 preSum 。 preSum 方法还能快速计算指定区间段 i ~ j 的元素之和。它的计算方法是从左向右遍历数组，当遍历到数组的 i 位置时， preSum 表示 i 位置左边的元素之和。
假设数组长度为 N ，我们定义一个长度为 N+1 的 preSum 数组， preSum[i] 表示该元素左边所有元素之和（不包含当前元素）。然后遍历一次数组，累加区间 [0, i) 范围内的元素，可以得到 preSum 数组。代码如下：
N = len(nums)
preSum = range(N + 1)
for i in range(N):
preSum[i + 1] = preSum[i] + nums[i]
print(preSum)
1 2 3 4 5
利用preSum 数组，可以在 O(1) 的时间内快速求出 nums 任意区间 [i, j] (两端都包含) 的各元素之和。
sum(i, j) = preSum[i + 1] - preSum[j]
综合以上的思路，我们的想法可以先求 preSum ，然后使用一个 0 ~ k 的遍历表示从左边拿走的元素数，然后根据窗口大小 windowSize = N - k ，利用 preSum 快速求窗口内元素之和。
对应的Python 代码如下。
class Solution(object):
def maxScore(self, cardPoints, k):
"""
:type cardPoints: List[int]
:type k: int
:rtype: int
"""
N = len(cardPoints)
preSum = [0] * (N + 1)
for i in range(N):
preSum[i + 1] = preSum[i] + cardPoints[i]
res = float("inf")
windowSize = N - k
for i in range(k + 1):
res = min(res, preSum[windowSize + i] - preSum[i])
return preSum[N] - res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
滑动窗口
在上面的 preSum 中，我们已经想到了，抽走的卡牌点数之和 = cardPoints 所有元素之和 - 剩余的中间部分元素之和。在 preSum 的代码里，我们是模拟了从左边拿走 i 个卡牌的过程。事实上，我们也可以直接求剩余的中间部分元素之和的最小值。只要剩余的卡牌点数之和最小，那么抽走的卡牌点数之和就最大！
求一个固定大小的窗口中所有元素之和的最小值——这是一个滑动窗口问题！与这个问题非常类似的就是前几天的每日一题 643. 子数组最大平均数 Iopen in new window。巧了，当时我的题解open in new window也是 preSum 和 滑动窗口 两种做法！
把剩余的中间部分元素抽象成长度固定为 windowSize = N - k 的滑动窗口。当每次窗口右移的时候，需要把右边的新位置 加到 窗口中的 和 中，把左边被移除的位置从窗口的 和 中 减掉。这样窗口里面所有元素的 和 是准确的，我们求出最大的和，最终除以 k 得到最大平均数。
这个方法只用遍历一次数组。
需要注意的是，需要根据 i 的位置，计算滑动窗口是否开始、是否要移除最左边元素：
- 当 i >`= windowSize 时，为了固定窗口的元素是 k 个，每次移动时需要将 i - windowSize 位置的元素移除。
- 当 i >`= windowSize - 1 时，滑动窗口内的元素刚好是 k 个，开始计算滑动窗口的最小和。
最后，用 cardPoints 的所有元素之和，减去滑动窗口内的最小元素和，就是拿走的卡牌的最大点数。
使用Python2 写的代码如下。
class Solution(object):
def maxScore(self, cardPoints, k):
"""
:type cardPoints: List[int]
:type k: int
:rtype: int
"""
N = len(cardPoints)
windowSize = N - k 窗口的大小
sums = 0
res = float("inf") 正无穷大
for i in range(N):
sums += cardPoints[i]
if i >= windowSize:
sums -= cardPoints[i - windowSize]
if i >= windowSize - 1:
res = min(res, sums)
return sum(cardPoints) - res
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
刷题心得
1、 今天这个题目，难点还是需要把抽取卡牌的问题转变为一个滑动窗口的问题；
2、 问题抽象之后，preSum和滑动窗口两种解法就已经呼之欲出了；
3、 每日一题的作用再次凸显，同一类题目都是换汤不换药，学会思路和套路之后，就很快秒杀！；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发