LC 1996. 游戏中弱角色的数量

题目描述

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

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

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

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

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

返回 弱角色 的数量。

示例 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^5$
• $properties[i].length == 2$
• $1 <= attacki, defensei <= 10^5$

---

排序 + 贪心 + 计数

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

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

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

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

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

代码：

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(n)$。整体复杂度为 $O(n\log{n})$
• 空间复杂度：$O(\log{n})$

---

最后

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

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

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

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