点排序

题目描述：

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

输入描述:

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。
对于 50%的数据,  1 <= N <= 10000;
对于 100%的数据, 1 <= N <= 500000;

输出描述:

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

示例1

输入

5
1 2
5 3
4 6
7 5
9 0

输出

4 6
7 5
9 0

思路:

代码:

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
struct node{
    int x;
    int y;
};
bool cmp(struct node a,struct node b){
    if(a.x<b.x){
        return true;
    }else{
        return false;
    }
}
int max(int a,int b){
    if(a>b){
        return a;
    }else{
        return b;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    struct node node1[n];
    for(int i=0;i<n;i++){
        scanf("%d%d",&node1[i].x,&node1[i].y);
    }
    sort(node1,node1+n,cmp);
    int maxNum[n];
    memset(maxNum,0,sizeof(maxNum));
    maxNum[n-1] = node1[n-1].y;
    //找出这个点到最后的数中最大数
    for(int i=n-2;i>=0;i--){
        maxNum[i] = max(maxNum[i+1],node1[i].y);
    }
    for(int i=0;i<n;i++){
        if(node1[i].y==maxNum[i]){
            printf("%d %d\n",node1[i].x,node1[i].y);
        }
    }
}

代码效率：

运行时间：207ms, 超过89.17%用C++提交的代码
占用内存：19556KB, 超过27.91%用C++提交的代码