题目

类型：贪心

解题思路

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

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

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

由于统计的是「严格弱角色」，因此在从前往后处理 ps 过程中，要将第一维度（攻击力）相同的作为一组进行处理，假设 [i, j) 为第一维度（攻击力）相同的连续段，假设当前处理到连续段 [i, j) 中的第 k 个角色 ps[k]，那么 ps[k]为弱角色的充要条件为：
1、存在比 ps[k][0] 攻击力高的角色，由于先按照了攻击力进行排序，同时又是按照攻击相同为一组进行处理，因此这等价于当前连续段 [i, j)不是第一组，即
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;
            while (j < n && ps[j][0] == ps[i][0]) {
                if (i != 0 && ps[j][1] < max) ans++;
                j++;
            }
            max = Math.max(max, ps[i][1]); i = j;
        }
        return ans;
    }
}