你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。给你一个二维整数数组 properties ，其中 properties[i] = [attacki, defensei] 表示游戏中第 i 个角色的属性。

如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，那么 attackj > attacki 且 defensej > 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 <= 105 properties[i].length == 2 1 <= attacki, defensei <= 105

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties,(o1,o2)->{

            return (o1[0]!=o2[0])?(o2[0]-o1[0]):(o1[1]-o2[1]);
        });
       
        int maxdef=0,cnt=0;
        for(int []pok:properties){
            // System.out.println(pok[0]+" "+pok[1]);
            if(pok[1]>=maxdef){
                maxdef=pok[1];
            }else{
                cnt++;
            }
        }
        return cnt;
    }
}

想了很久，发现官方题解的排序思路是最容易理解的，

1
2
3
4
5
6

10 4
10 7
7 5
7 9
7 10
6 9

排序以后就很清晰，从上到下遍历，记录最大的防御值，随后每次访问的角色中，攻击值是小于前面的，只需要判断防御值是否小于前面记录的最大防御值，由于相同攻击值时，防御值是递增的，所以不会出现更新完maxdef以后遇到同攻击值但防御值小于maxdef的问题。

然后由看到https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game/solution/1996you-xi-zhong-de-ruo-jiao-se-zui-da-z-so68/这个题解，用O(n+C)的时间完成了等价排序的操作，我觉得很妙。

 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

class Solution {

    int tables[]=new int[100002];
    public int numberOfWeakCharacters(int[][] properties) {
      
       
        int maxack=0,cnt=0,a,b;
        for(int []pok:properties){
            // System.out.println(pok[0]+" "+pok[1]);
            a=pok[0];
            b=pok[1];
            maxack=Math.max(a,maxack);
            if(b>tables[a]) tables[a]=b;
        }
        for(int i=maxack;i>0;i--){
            if(tables[i]>tables[i-1]) tables[i-1]=tables[i];

        }
        for(int []pok:properties){
            if(pok[1]<tables[pok[0]+1]) cnt++;
        }
        return cnt;


    }
}

总体思路是维护一张记录每个不同攻击值对应的最大防御值的表table

比如

1

   [[7,9],[10,7],[6,9],[10,4],[7,5],[7,10]]
0
1
2
3
4
5
6 9
7 9->10
8
9
10 7

知道每个攻击值对应的最大值的话，对于每个角色比如[7,1]，搜索比他攻击值大的，比如10.然后判断角色[7,1]的防御值（1）是否小于10对应 的最大防御值（7），满足弱角色的定义。

那么如何简化这个搜索的过程呢？可以想到类似前缀和的思路，在table中每个攻击值对应比他大或他的最大防御值

0 9
1 9
2 9
3 9
4 9
5 9
6 9
7 10
8 7
9 7
10 7

然后对每一个角色按照这张表做判断

1

   [[7,9],[10,7],[6,9],[10,4],[7,5],[7,10]]

比如[7,9]判断攻击值为7+1对应的防御值（7）和他的防御值（9），该角色不满足

[10,7]判断攻击值为10+1对应的防御值（0）和他的防御值（7），该角色不满足

[6,9]判断攻击值为6+1对应的防御值（10）和他的防御值（9），该角色满足

[10,4]不满足

[7,5]判断攻击值为7+1对应的防御值（7）和他的防御值（5），该角色满足 [7,10]判断攻击值为7+1对应的防御值（7）和他的防御值（10），该角色不满足

所以有了这张表，对于任意一个角色，我们可以查询，比该角色攻击值大1对应的防御值，和该角色的防御值做比较，即可得出是否满足弱角色的定义。