无矛盾的最佳球队

标签: 数组 动态规划 排序

难度: Medium

假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。

然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。

给你两个列表 scores 和 ages，其中每组 scores[i] 和 ages[i] 表示第 i 名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。

 

示例 1：

输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选中所有球员。

示例 2：

输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。

示例 3：

输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。

 

提示：

  • 1 <= scores.length, ages.length <= 1000
  • scores.length == ages.length
  • 1 <= scores[i] <= 106
  • 1 <= ages[i] <= 1000

Submission

运行时间: 100 ms

内存: 16.3 MB

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        u = max(ages)
        t = [0] * (u + 1)

        # 返回 max(max_sum[:i+1])
        def query(i: int) -> int:
            mx = 0
            while i:
                mx = max(mx, t[i])
                i &= i - 1
            return mx

        # 更新 max_sum[i] 为 mx
        def update(i: int, mx: int) -> None:
            while i < len(t):
                t[i] = max(t[i], mx)
                i += i & -i

        for score, age in sorted(zip(scores, ages)):
            update(age, query(age) + score)
        return query(u)

Explain

本题解采用了结合排序和树状数组（Binary Indexed Tree, BIT）的动态规划方法。首先，通过将球员按照年龄排序（如果年龄相同则按分数排序），确保能够以非降序处理球员。这样，在处理每个球员时，可以保证其之前的球员要么年龄小于等于当前球员，要么年龄相同但分数不大于当前球员。然后，使用树状数组来维护不同年龄下可达到的最高分数总和。对于每个球员，通过树状数组查询当前年龄可达到的最大分数，并更新该年龄的分数总和。最后，通过查询最大年龄的信息，得到最大分数总和。

时间复杂度: O(n log n + n log(maxAge))

空间复杂度: O(maxAge + n)

class Solution:
    def bestTeamScore(self, scores: List[int], ages: List[int]) -> int:
        u = max(ages)
        t = [0] * (u + 1)

        def query(i: int) -> int:
            # 查询树状数组中从1到i的最大值
            mx = 0
            while i:
                mx = max(mx, t[i])
                i &= i - 1
            return mx

        def update(i: int, mx: int) -> None:
            # 更新树状数组，将位置i的值更新为当前路径的最大值
            while i < len(t):
                t[i] = max(t[i], mx)
                i += i & -i

        # 对球员按年龄和分数排序，确保处理顺序符合题目要求
        for score, age in sorted(zip(scores, ages)):
            # 对于每个球员，更新其年龄对应的最大分数
            update(age, query(age) + score)
        # 查询最大年龄对应的最大分数总和
        return query(u)

Explore

球员的排序是为了保证处理球员时，可以通过动态规划的方式逐步构建最佳球队。排序规则是首先按年龄升序排序，如果年龄相同，则按分数升序排序。这样做的目的是在处理每个球员时，可以保证之前处理的球员要么年龄小于等于当前球员，要么年龄相同但分数不大于当前球员。这种排序方式确保了在使用动态规划时，可以正确地依赖之前的状态来更新当前状态，从而找到最优解。

在这个题解中，树状数组中的每个位置代表了对应年龄的最高分数总和。具体来说，如果树状数组的索引为i，则该位置存储的是年龄为i的球员组成的球队可以达到的最高分数总和。这种结构允许我们通过高效的更新和查询操作，快速地计算和更新不同年龄下的球队的最高分数总和。

查询函数`query()`的实现逻辑是从指定的年龄开始，向下迭代到年龄1，通过树状数组中的链接结构逐个查询更小的年龄范围，累计这些范围内的最大分数总和。在每次迭代中，它使用`i &= i - 1`来移动到下一个需要查询的索引。这种方法确保了能够获取到从年龄1到当前年龄i的球员组成的球队可能达到的最大分数总和。

更新函数`update()`的作用是将树状数组中的某个特定年龄的最高分数总和更新为新的更高值。它通过从指定的年龄索引开始，逐步向数组的较高索引移动，并在每个步骤中更新存储的分数总和。这是通过`i += i & -i`实现的，该操作确保了能逐步覆盖所有包含该年龄的范围。这种更新保证了在任何给定的年龄点，树状数组都能反映出到目前为止可能组成的最佳球队的最高分数总和。