LeetCode 1996. 游戏中弱角色的数量*

具体思路：

之前见过一道原题；

卡在了单调栈上的第二维度排序上；

具体代码：

1.单调栈：

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int n=properties.size();
        vector<int>arr;
        sort(properties.begin(),properties.end(),[](vector<int>& a,vector<int>& b){
            if(a[0]==b[0])
                return a[1]>b[1];
            else
                return a[0]<b[0];
        });
        for(int i=0;i<n;i++){
            arr.push_back(properties[i][1]);
        }
        stack<int>st;
        int cnt=0;
        for(int i=0;i<arr.size();i++){
            while(!st.empty()&&arr[st.top()]<arr[i]){
                int index=st.top();
                st.pop();
                cnt++;
            }
            st.push(i);
        }
        return cnt;
    }
};

2.排序方法：

class Solution {
public:
    int numberOfWeakCharacters(vector<vector<int>>& properties) {
        int n=properties.size();
        vector<int>arr;
        sort(properties.begin(),properties.end(),[](vector<int>& a,vector<int>& b){
            if(a[0]==b[0])
                return a[1]<b[1];
            else
                return a[0]>b[0];
        });
        int maxdef=0;
        int cnt=0;
        for(int i=0;i<properties.size();i++){
            if(maxdef>properties[i][1]){
                cnt++;
            }
            maxdef=max(maxdef,properties[i][1]);
        }
        return cnt;
    }
};