leetcode 1996 游戏中弱角色的数量

题意简述

给出一些角色，每个角色有$ATK$和$DEF$属性，若存在另一个角色，它的两个属性值都严格大于自己的两个属性值，称自己为弱角色。求出这些角色中弱角色个数。

算法分析

如果属性仅有一个，直接排序或记录最大值，比较就可以得到答案。考虑对其中一个属性$ATK$排序，按降序遍历每一个角色，并记录已遍历过的角色的$DEF$最大值$maxD$，如果当前角色的$DEF$值小于$maxD$，答案加一。同时还需考虑$ATK$属性相同的那些角色，如果没有顺序地遍历这些角色，可能会出现$DEF$较小的角色被误认为弱角色的情况。这种情况当$maxD$来自于前面某一个$ATK$与当前角色$ATK$相同的角色时出现。所以对于$ATK$相同的角色，应该按照$DEF$升序排序。

代码实现

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        sort(properties.begin(), properties.end(), [](vector<int>& a, vector<int>& b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
        int maxD = 0;
        int ans = 0;
        for (auto player : properties) {
            if (player[1] < maxD) ans++;
            else maxD = player[1];
        }
        return ans;
    }
};

另解

二维偏序，线段树，挖坑