leetcode
leetcode 1301 ~ 1350
可获得的最大点数

可获得的最大点数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
算法为何选择滑动窗口来寻找中间最小点数序列,而非直接在两端查找最大点数组合?
这个问题的关键在于,我们需要从卡牌的两端选择卡牌以最大化得分,这等价于在卡牌序列中留下一个最小点数的连续子序列。如果我们尝试直接从两端寻找最大点数组合,将涉及到极大的组合可能性,这会导致时间复杂度过高,尤其是当 k 的值较大时。滑动窗口方法可以有效地在 O(n) 时间内找到这个最小的连续子序列,因为通过逐步移动窗口,我们可以在不重复计算的情况下,快速更新窗口内的点数总和。
🦆
你如何确定滑动窗口的宽度应该是 n-k 而不是其他值?
在题目中,我们的目标是从卡牌的两端取出总共 k 张卡牌,这意味着留在卡牌序列中的卡牌数量为 n-k。为了使从两端取出的卡牌点数最大,我们需要使留在序列中的这部分卡牌的点数总和最小。因此,滑动窗口的宽度应该被设定为 n-k,这样窗口覆盖的就是留在序列中的卡牌,我们通过寻找这个宽度的窗口中的最小点数和来达到目的。
🦆
在实现滑动窗口时,为什么初始窗口的和只包含从索引0开始的 width 个元素,而不是任意位置的 width 个连续元素?
在初始化滑动窗口时,从索引0开始的 width 个元素作为起始点是出于简化实现的考虑。这样可以从序列的开始处逐步向右滑动窗口,直到窗口到达序列的末端。这种方法保证了每个可能的窗口位置都被考虑到,同时简化了逻辑,因为我们无需考虑窗口的初始位置。从任意位置开始并不会提供额外的优势,且会使实现复杂化。
🦆
该算法在更新滑动窗口的最小和时,为什么只用了简单的比较和赋值操作,这种方法在所有情况下都是有效的吗?
该算法在更新滑动窗口的最小和时使用简单的比较和赋值操作是有效的,因为我们的目标是找到所有可能的窗口和中的最小值。在窗口逐步滑动过程中,我们对每个新的窗口和进行计算,并与当前记录的最小和进行比较。如果新的窗口和更小,则更新最小和。这种方法是有效的,因为它保证了在滑动窗口覆盖整个序列的过程中,每次计算后我们都有当前最小的连续子序列和。这一点在所有情况下都保持有效,无需复杂的数据结构或额外的逻辑。

相关问题