1996. The Number of Weak Characters in the Game

Question

You are playing a game that contains multiple characters, and each of the characters has two main properties: attack and defense. You are given a 2D integer array properties where properties[i] = [attack<sub>i</sub>, defense<sub>i</sub>] represents the properties of the i<sup>th</sup> character in the game.

A character is said to be weak if any other character has both attack and defense levels strictly greater than this character’s attack and defense levels. More formally, a character i is said to be weak if there exists another character j where attack<sub>j</sub><span> </span>> attack<sub>i</sub> and defense<sub>j</sub><span> </span>> defense<sub>i</sub>.

Return the number of weak characters.

Solution

本题与354. Russian Doll Envelopes相近。

首先对数组进行排序，根据角色的attack数值降序排序，如果两者的attack数值相等，则根据两者的defence升序排序。

记录一个遍历过的最大defence数值maxDefence，遍历数组，如果当前maxDef大于角色的防御值，则此时当前遍历角色的attack与defence均严格小于上一个计算的角色，因此count加一。
否则更新maxDef。

*由于attack是降序的，因此可以确定遍历时下一组数组的attack一定更弱。（由于相同attack的角色是根据defence升序排列，因此记录maxDef时会逐个更新maxDef的值。）

Code

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        int count = 0, maxDef = Integer.MIN_VALUE;
            
        Arrays.sort(properties, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return a[1] - b[1];
                return b[0] - a[0];
            }
        });
        
        for(int[] character : properties){
            if(maxDef > character[1]) count++;
            else maxDef = character[1];
        }
        return count;
    }
}