1996.游戏中弱角色的数量

链接：1996.游戏中弱角色的数量
难度：Medium
标签：栈、贪心、数组、排序、单调栈
简介：返回 弱角色 的数量。

题解 1 - cpp

• 编辑时间：2022-01-28
• 执行用时：696ms
• 内存消耗：169.1MB
• 编程语言：cpp
• 解法介绍：排序后用堆比较。

class Solution {
   public:
    int numberOfWeakCharacters(vector<vector<int>> &properties) {
        int ans = 0;
        map<int, vector<int>> m;
        priority_queue<int, vector<int>, greater<int>> q;
        for (auto &data : properties) m[data[0]].push_back(data[1]);
        for (auto &data : m) {
            sort(data.second.begin(), data.second.end(), greater<int>());
            while (q.size() && q.top() < data.second[0]) q.pop(), ans++;
            for (auto &num : data.second) q.push(num);
        }
        return ans;
    }
};