(nice!!!)(LeetCode 每日一题) 3025. 人员站位的方案数 I (排序)

题目：3025. 人员站位的方案数 I

思路：排序，时间复杂度0(n^2)。
将数组points里的元素先按横坐标x升序排序，纵坐标y降序排序。第一层for循环枚举左上角的点，第二层for循环枚举右下角的点。细节看注释。

C++版本：

class Solution {
public:
    typedef pair<int,int> PII;
    static bool cmp(PII a,PII b){
        if(a.first==b.first) return b.second<a.second;
        return a.first<b.first;
    }
    int numberOfPairs(vector<vector<int>>& points) {
        vector<PII> v;
        for(auto item: points){
            v.push_back({item[0],item[1]});
        }
        // 将数组points里的元素先按横坐标x升序排序，纵坐标y降序排序
        sort(v.begin(),v.end(),cmp);
        int n=v.size();
        // 答案
        int ans=0;
        // 第一层for循环枚举左上角的点
        for(int i=0;i<n;i++){
        	// 右下角的点不能低于mx，否则会覆盖之前的点
            int mx=INT_MIN;
            // 第二层for循环枚举右下角的点
            for(int j=i+1;j<n;j++){
                if(v[i].first<=v[j].first && v[i].second>=v[j].second && v[j].second>mx){
                    ans++;
                    mx=v[j].second;
                } 
            }
        }
        return ans;

    }
};

JAVA版本：

class Solution {
    public int numberOfPairs(int[][] points) {
        Arrays.sort(points,(a,b) -> a[0]!=b[0] ? a[0]-b[0]:b[1]-a[1] );
        int ans=0;
        int n=points.length;
        for(int i=0;i<n;i++){
            int mx=Integer.MIN_VALUE;
            for(int j=i+1;j<n;j++){
                if(points[i][1]>=points[j][1]&&points[j][1]>mx){
                    ans++;
                    mx=points[j][1];
                }
            }
        }
        return ans;
    }
}

GO版本：

func numberOfPairs(points [][]int) int {
    slices.SortFunc(points,func(a,b []int)int{
        return cmp.Or(a[0]-b[0],b[1]-a[1])
    })
    ans:=0
    n:=len(points)
    for i:=0;i<n;i++ {
        mx:=math.MinInt
        for j:=i+1;j<n;j++ {
            if points[i][1]>=points[j][1] && points[j][1]>mx {
                ans++
                mx=points[j][1]
            }
        }
    }
    return ans
}