leetcode 1996. 游戏中弱角色的数量(排序的魅力)-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 1996. 游戏中弱角色的数量(排序的魅力)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目
题意: 给定n个人的攻击力和防御力，对于一个人来说，如果存在某个人的攻击力和防御力都比他高，那么称这个人为弱角色。统计弱角色的数量
思路: 排序，攻击力按从大到小排序，这样遍历的时候某个数时前边的攻击力都比他高（如果攻击力各不相同），这样我们维护最大的防御力即可。难处理的是攻击力相同怎么办，有可能维护的最大防御力是相同攻击力的人，这样就统计错误。可以对于攻击力相同的，按照防御力从小到大排序，这样可以保证维护的最大防御力的人的攻击力是严格高于当前人的攻击力的。因为攻击力相同的人是放在一起的，然后防御力从小到大可以保证当前这个人前边与他攻击力相同的人的防御力比他低，这样就保证了维护的最大防御力的人的攻击力是严格高于当前人的攻击力的。
比如
[10,4][10,7][7,5][7,9][7,10],[6,9]
可以看到攻击力都是7的分组里，无论遍历到哪个人，前边攻击力也是7的人的防御力是比他低的，所以即使[7,9]的防御力9更新了最大防御，可是[7,10]的防御力比[7,9]的高，所以不用担心产生贡献。所以不会出现同是攻击力为7的人之间对答案产生贡献。
代码:文章来源地址https://www.toymoban.com/news/detail-666574.html

class Solution {
public:
    static bool cmp(vector<int>& a,vector<int>& b)
    {
        int x1 = a[0],x2 = b[0];
        int y1 = a[1],y2 = b[1];
        if(x1 != x2) return x1 > x2;
        return y1 < y2;
    }
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        sort(properties.begin(),properties.end(),cmp);
        int mxy = 0;
        int ans = 0;
        for(int i=0;i<properties.size();++i)
        {
            int x = properties[i][0];
            int y = properties[i][1];
            if(y < mxy)
            {
                ans ++ ;
            }
            else 
            {
                mxy = y;
            }
        }
        return ans;
    }
};