可获得的最大点数
难度:
标签:
题目描述
代码结果
运行时间: 44 ms, 内存: 26.0 MB
/*
题目思路:
我们可以使用Java Streams来处理这个问题。首先计算前k张牌的点数和,然后使用流操作进行滑动窗口的计算来找出最大点数。
*/
import java.util.stream.IntStream;
public class Solution {
public int maxScore(int[] cardPoints, int k) {
int n = cardPoints.length;
// 计算前k张牌的点数和
int total = IntStream.range(0, k).map(i -> cardPoints[i]).sum();
// 如果k等于卡牌的总数,直接返回总和
if (k == n) return total;
// 初始化最大点数为前k张牌的点数和
int maxScore = total;
// 使用滑动窗口计算从左边取i张牌和从右边取k-i张牌的组合
for (int i = 0; i < k; i++) {
total += cardPoints[n - 1 - i] - cardPoints[k - 1 - i];
maxScore = Math.max(maxScore, total);
}
return maxScore;
}
}
解释
方法:
这个题解采用了滑动窗口的方法来优化求解过程。首先计算卡牌总点数。然后,由于我们要从卡牌序列的两端取出共计 k 张卡牌,可以等效地看作从中间留下长度为 n-k 的连续卡牌子序列,使得这个子序列的点数最小,从而使得取出的 k 张卡牌的点数最大。具体实现中,首先计算了整个卡牌的点数总和,然后通过滑动窗口计算所有可能的长度为 n-k 的子序列的点数和,并找出这些和中的最小值。最后,用总点数减去这个最小的子序列和,就得到了能够从两端取 k 张卡牌得到的最大点数。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
算法为何选择滑动窗口来寻找中间最小点数序列,而非直接在两端查找最大点数组合?
▷🦆
你如何确定滑动窗口的宽度应该是 n-k 而不是其他值?
▷🦆
在实现滑动窗口时,为什么初始窗口的和只包含从索引0开始的 width 个元素,而不是任意位置的 width 个连续元素?
▷🦆
该算法在更新滑动窗口的最小和时,为什么只用了简单的比较和赋值操作,这种方法在所有情况下都是有效的吗?
▷