1996. 游戏中弱角色的数量 : 排序成组贪心计数运用题

题目描述

这是 LeetCode 上的 1996. 游戏中弱角色的数量 ，难度为 中等。

Tag : 「贪心」

你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。

给你一个二维整数数组 properties，其中 properties[i] = [attack_i, defense_i]properties[i]=[attacki,defensei] 表示游戏中第 ii 个角色的属性。

如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。

更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attack_j > attack_iattackj>attacki 且 defense_j > defense_idefensej>defensei 。

返回 弱角色 的数量。

示例 1：

输入：properties = [[5,5],[6,3],[3,6]]
输出：0
解释：不存在攻击和防御都严格高于其他角色的角色。
复制代码

示例 2：

输入：properties = [[2,2],[3,3]]
输出：1
解释：第一个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
复制代码

示例 3：

输入：properties = [[1,5],[10,4],[4,3]]
输出：1
解释：第三个角色是弱角色，因为第二个角色的攻击和防御严格大于该角色。
复制代码

提示：

• 2 <= properties.length <= 10^52<=properties.length<=105
• properties[i].length == 2properties[i].length==2
• 1 <= attacki, defensei <= 10^51<=attacki,defensei<=105

排序 + 贪心 + 计数

为了方便，我们使用 ps 来代指 properties。

决定角色「强弱」的维度有两个，同时由于我们只关心某个角色是否为弱角色，而不关心有多少比其（严格）强的角色有多少个。

因此我们先对 ps 进行排序：优先根据第一维度（攻击力）排序，在第一维度（攻击力）相同时，根据第二维度（防御力）进行排序。

由于我们统计的是「严格弱角色」，因此在从前往后处理 ps 过程中，要将第一维度（攻击力）相同的作为一组进行处理，假设 [i, j)[i,j) 为第一维度（攻击力）相同的连续段，假设当前处理到连续段 [i, j)[i,j) 中的第 kk 个角色 ps[k]ps[k]，那么 ps[k]ps[k] 为弱角色的充要条件为：

1. 存在比 ps[k][0]ps[k][0] 攻击力高的角色，由于我们先按照了攻击力进行排序，同时又是按照攻击相同为一组进行处理，因此这等价于当前连续段 [i, j)[i,j) 不是第一组，即 i \neq 0i=0；
2. 在满足 11 的前提下，存在防御力比 ps[k][1]ps[k][1] 高的角色，由于要求弱角色为「严格」，因此我们只能在之前的组（攻击力比 ps[k][0]ps[k][0] 大的相同连续段）去找。这意味着我们在遍历过程中需要贪心地维护一个防御力的最大值 \maxmax，并在处理完相同连续段后尝试对其进行更新。

代码：

class Solution {
    public int numberOfWeakCharacters(int[][] ps) {
        int n = ps.length, ans = 0;
        Arrays.sort(ps, (a, b)->{
            if (a[0] != b[0]) return b[0] - a[0];
            return b[1] - a[1];
        });
        for (int i = 0, max = ps[0][1]; i < n; ) {
            int j = i, cur = max;
            while (j < n && ps[j][0] == ps[i][0]) {
                if (i != 0 && ps[j][1] < max) ans++;
                cur = Math.max(cur, ps[j][1]);
                j++;
            }
            i = j; max = cur;
        }
        return ans;
    }
}
复制代码

• 时间复杂度：排序的复杂度为 O(n\log{n})O(nlogn)；统计答案复杂度为 O(n)O(n)。整体复杂度为 O(n\log{n})O(nlogn)
• 空间复杂度：O(\log{n})O(logn)

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1996 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。