LC.P1626[无矛盾的最佳球队]

题目描述

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

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

给你两个列表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

方法一：排序+动态规划

先将球员按照分数从小到大排序，如果分数相同，则按照年龄从小到大排序。

接着使用动态规划求解，定义f[i]表示以排序后的第i个球员作为最后一个球员的最大得分。

对于f[i]，枚举 0 <= j < i，如果第i个球员的年龄大于第j个球员的年龄，则f[i]可从f[j]转移而来，状态转移方程为 f[i] = max(f[i], f[j])。然后将第i个球员的分数加到f[i]中，即f[i] += score[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length, ans = 0;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) arr[i] = new int[]{scores[i], ages[i]};
        // 按分数从小到大排序，若分数相同，则按年龄从小到大排序
        Arrays.sort(arr, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        int[] f = new int[n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (arr[i][1] >= arr[j][1]) f[i] = Math.max(f[i], f[j]);
            }
            f[i] += arr[i][0];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n^2)$
  • 空间复杂度：O(n)

方法二：树状数组

通过方法一，可利用树状数组来维护以每一个球员作为组建球队的最后一名球员的年龄的最大队伍分数。在方法一的动态规划转移方程中，f[i]的求解只需要知道当前树状数组中以年龄区间为[0, arr[0][1]]结尾的组建队伍的最大分数即可。可将每一个状态的时间复杂度从O(n)降到O(logn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    int[] tree;
    int maxAge;

    private int lowbit(int x) {
        return x & -x;
    }

    private void update(int x, int val) {
        for (int i = x; i <= maxAge; i += lowbit(i)) {
            tree[i] = Math.max(tree[i], val);
        }
    }

    private int query(int x) {
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit(i)) {
            ans = Math.max(ans, tree[i]);
        }
        return ans;
    }

    public int bestTeamScore(int[] scores, int[] ages) {
        int n = scores.length, ans = 0;
        maxAge = Arrays.stream(ages).max().getAsInt();
        tree = new int[maxAge + 1];
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; ++i) arr[i] = new int[]{scores[i], ages[i]};
        // 按分数从小到大排序，若分数相同，则按年龄从小到大排序
        Arrays.sort(arr, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        for (int i = 0; i < n; ++i) {
            int score = arr[i][0], age = arr[i][1];
            int cur = score + query(age);
            update(age, cur);
            ans = Math.max(ans, cur);
        }
        return ans;
    }
}
  • 时间复杂度：$O(nlogn)$
  • 空间复杂度：$O(n)$