# 1996. The Number of Weak Characters in the Game
###### tags: `Leetcode` `Medium` `Greedy` `Sorting`
Link: https://leetcode.com/problems/the-number-of-weak-characters-in-the-game/
## 思路
### 思路一 Greedy+Sorting
先不考虑武力值相同的情况
我们按照武力值(```property[0]```)排序，我们只需要在这个序列中查看有多少靠前的人的防御值也比靠后的人低即可。我们可以用一个栈，维护一个递减的防御力。如果新元素的防御力高，那么栈顶元素都是弱角色（因为攻击力和防御力都不及后来的新元素），可以不断退栈直至防御力不输给新元素。可以想象，只有递增的攻击力（排序）同时搭配递减的防御力（栈），才能保证序列的增长和元素的共存。
接下来我们需要考虑如何应对攻击力相同的人，将相同攻击力的人按照防御力从大到小排列。这样这些人逐个加入栈的时候，就不会触发弹栈操作。
### 思路二
自己想到的方法
先排序 倒序查看每个array 然后group by first property
- 如果遇到一个array和之前的first property不同（切换group）记录上一个group的最大second property(prevMax)和现在遍历过的所有array的second property(maxSecond)比较保留最大的一个
- 如果相同 更新prevMax
- always比较当前的second property和maxSecond 如果前者小，ans+1 (当前property和maxSecond永远不会有相同的first property)
## Code
### 思路一 Greedy+Sorting

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a, b) -> (b[0] == a[0]) ? (a[1] - b[1]) : b[0] - a[0]);
        int max = 0;
        int ans = 0;
        for(int i = 0;i < properties.length;i++){
            if (properties[i][1] < max) {
                ans++;
            }
            max = Math.max(max, properties[i][1]);
        }
        return ans;
    }
}

### 思路二

class Solution {
    public int numberOfWeakCharacters(int[][] properties) {
        Arrays.sort(properties, (a,b)->(a[0]-b[0]));
        int maxSecond = Integer.MIN_VALUE;
        int prevFirst = -1;
        int prevMax = 0;
        int ans = 0;
        for(int i=properties.length-1; i>=0;i--){
            int[] property = properties[i];
            if(prevFirst != property[0]){
                maxSecond = Math.max(maxSecond, prevMax);
                prevMax = property[1];
            }
            else{
                prevMax = Math.max(prevMax, property[1]);
            }
            
            if(property[1] < maxSecond){
                ans += 1;
            }
            
            prevFirst = property[0];
        }
        return ans;
    }
}