首页 > 试题广场 >

最大点集

[编程题]最大点集
  • 热度指数：4885 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解

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

 

如下图：实心点为满足条件的点的集合。

请实现代码找到集合P中的所有”最大“点的集合并输出。


输入描述:
第一行输入点集的个数N， 接下来N行，每行两个数字代表点的X轴和Y轴。1 ≤ n ≤ 500000


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

输入

5
1 2
5 3
4 6
7 5
9 0

输出

4 6
7 5
9 0

备注:
输出结果按照x轴排序
算法知识视频讲解
添加回答
木析头像 木析
“最大点”（假设坐标为(x0,y0)）就是不存在其他的点(x,y)使得 x>x0 && y>y0
先按照x进行排序，从右往左遍历，每个点后面的点都位于该点右侧，即存在x>x0，再来判断这些点中是否存在y>y0的情况即可。 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<math.h>
#include<algorithm>
#include<stack>
using namespace std;
int main()
{
    int n;
    cin>>n;
    vector<vector<int>> arr(n,vector<int>(2,0));
    for(int i=0;i<n;i++) {
        cin>>arr[i][0];
        cin>>arr[i][1];
    }
    sort(arr.begin(),arr.end(),[&](vector<int> &a, vector<int>& b){
        return a[0]<b[0];
    });
    stack<vector<int>> s; //因为要求输出结果按照x轴排序，因而使用一个栈
    s.push(arr[n-1]); //因为最右边（x最大）的点必然是没有其他元素可以使x>x0 && y>y0的
    int maxy=arr[n-1][1];
    for(int i=n-2;i>=0;i--) {
        if(arr[i][1]<maxy) {
            //该点右边的节点中存在纵坐标大于该点纵坐标的，即存在点(x,y)，使x>x0 && y>y0
            continue;
        }
        s.push(arr[i]);
        maxy=max(maxy,arr[i][1]);
    }
    while(!s.empty()) {
        vector<int> cur=s.top(); s.pop();
        cout<<cur[0]<<" "<<cur[1]<<endl;
    }
    return 0;
}


发表于 2021-05-12 17:15:06 回复(0)
皮蛋秀柚秋头像 皮蛋秀柚秋 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        ArrayList<Point>list = new ArrayList<>();
        int x,y;
        for(int i=0;i<n;++i){
            x = scan.nextInt();
            y = scan.nextInt();
            list.add(new Point(x,y));
        }
        Stack<Point>stack = new Stack<>();
        int maxY = Integer.MIN_VALUE;
        Collections.sort(list);
        for(int i=0;i<list.size();++i){
            if(list.get(i).y>=maxY){
                stack.push(list.get(i));
                maxY = list.get(i).y;
            }
        }
        while(!stack.isEmpty()){
            Point p = stack.pop();
            System.out.printf("%d %d\n",p.x,p.y);
        }
        
        
    }
    static class Point implements Comparable{
        public int x,y;
        public Point(int x,int y){
            this.x = x;
            this.y = y;
        }
        // 按X轴从大到小排，之后只比较Y值即可
        @Override
        public int compareTo(Object o){
            Point p = (Point)o;
            return p.x-this.x;
        }
    }
}

发表于 2020-07-11 20:34:46 回复(0)
Python
冷遇"头像 冷遇"
def find():
    num = int(input())
    points = []
    result = []
    for i in range(num):
        x,y = map(int, input().split())
        points.append((x,y))
    points.sort()
    result.append(points[-1])
    target = points[-1][1]
    for i in range(num-2,-1,-1):
        if points[i][1] > target:
            target = points[i][1]
            result.insert(0,points[i])
    for i in range(len(result)):
        print(result[i][0],result[i][1])

if __name__ == "__main__":
    find()

Python解题思路：首先不用考虑横纵坐标重合的情况下，将所有点排正序sort，那么最后一个点就是x坐标最大的点,将此点设为一个参照点。那么符合题目要求的点此时一定在参照点的左上方。然后一一倒序比对上一个点和参照点，把符合要求的点（即当前点y坐标大于参照点）保存到存放结果的数组中并设置成新的参照点。
发表于 2020-07-15 18:02:48 回复(1)
pein531头像 pein531
这题调大内存之后终于能AC了😂 
n = int(input())
points = []
for _ in range(n):
    points.append(list(map(int, input().split())))
points.sort(key=lambda x: x[0])
# 计算从i~n-1的数据点中纵坐标最大的值
maxY = [0]*n
maxY[n - 1] = points[n - 1][1]
for i in range(n - 2, -1, -1):
    maxY[i] = max(points[i][1], maxY[i + 1])
# 求最大点
for i in range(n - 1):
    if points[i][1] > maxY[i + 1]:
        print(str(points[i][0]) + " " + str(points[i][1]))
# 横坐标最大的点一定是“最大的”点
print(str(points[n - 1][0]) + " " + str(points[n - 1][1]))
发表于 2020-12-09 17:02:16 回复(2)
C/C++
Ver丶头像 Ver丶
坑点在于大量输出时printf()的效率远高于cout......
大概是从300ms与超时的水平
编辑于 2022-04-22 04:28:23 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

struct P{
    int x, y;
    bool operator < (const P &p) const{
        return y > p.y;
    }
};

int main(){
    int n, x, y, Max=0;
    scanf("%d", &n);
    P p[n];
    for(int i=0;i<n;i++)
        scanf("%d%d", &p[i].x, &p[i].y);
    sort(p, p+n);
    for(int i=0;i<n;i++){
        if(p[i].x > Max){
            Max = p[i].x;
            printf("%d %d\n", p[i].x, p[i].y);
        }
    }
    return 0;
}

发表于 2020-12-16 00:34:41 回复(1)
Python3
Jared_VIP头像 Jared_VIP
可惜超时了 
def ZJ13():
    n = int(input())
    points = []
    for i in range(n):
        points.append(list(map(int,input().split())))

    points.sort(key=lambda x:x[0],reverse=True)
    ans = []
    maxY = points[0][1]
    for item in points:
        if item[1]>=maxY:
            ans.append(item)
            maxY = item[1]
    for item in ans[::-1]:
        print(' '.join(map(str, item)))

if __name__ == '__main__':
    ZJ13()


编辑于 2023-12-29 11:39:58 回复(0)
给个好offer头像 给个好offer 
//卡数据，要用BufferedReader ，不然测评机里面过不过随缘


import java.util.*;
import java.io.*;
public class Main{
    public static void main (String[] args)throws Exception{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); 
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        int n = Integer.parseInt(reader.readLine());
        Integer[][] a=new Integer[n][2];
        int maxX=0;
        
        for(int i=0;i<n;i++){
            
            String[] s=reader.readLine().split(" ");
                 a[i][0]=Integer.parseInt(s[0]);;
            if(a[i][0]> maxX)
                maxX=a[i][0];
                  a[i][1]=Integer.parseInt(s[1]);;
           
            
        }
      
        Arrays.sort(a,new Comparator<Integer[]>(){
            @Override
            public int compare(Integer[] b,Integer[] c){
                return -(b[1]-c[1]);
            }
        });
        int start=-1,end=n-1;
        for(int i=0;i<n;i++){
            if(a[i][0]>start){
           
                start=a[i][0];
                System.out.println(a[i][0]+" "+a[i][1]);
            }
           
        }
    }


}

发表于 2021-04-20 20:45:36 回复(0)
C/C++
ASCII3头像 ASCII3 
#include<iostream>
#include<algorithm>

using namespace std;

class Xy
{
public:
    int x;
    int y;
};

bool cmp(Xy a, Xy b)
{
    return a.x < b.x;
}

int main()
{
    int n; cin >> n;
    Xy* arr;
    arr = new Xy[n];
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].x;
        cin >> arr[i].y;
    }
    sort(arr,arr+n,cmp);
    int flag = 0, num;
    for (int i = 0; i < n; i++)
    {
        flag = 0; num = arr[i].y;
        for (int j = i; j < n; j++)
        {
            if (num < arr[j].y)
            {
                flag = 1; break;
            }
        }
        if (flag == 0)
        {
            cout << arr[i].x << " " << arr[i].y << endl;
        }
    }
}
先对x轴从小到大排序，然后对每个点只要看它之后的点有没有纵坐标大于它的就好了，没有就输出
发表于 2021-03-30 21:54:29 回复(0)
C/C++
龙胆紫头像 龙胆紫
最笨的方法 
#include <iostream>
#include <algorithm>
using namespace std;
struct xy{
    int x;
    int y;
};
bool compare(xy n1,xy n2)
{
    return n1.y<n2.y;
}
bool compare2(xy n1,xy n2)
{
    return n1.x<n2.x;
}
int main()
{
    struct xy node[500000];
    struct xy copy1[500000]={0,0};
    int caseN,i,j,tag=0,max_y,tagy;
    cin>>caseN;
    for(i=0;i<caseN;i++)
    {
        cin>>node[i].x>>node[i].y;
    }
    for(i=0;i<caseN;i++)
    {
        copy1[i].x=-1;
        copy1[i].y=-1;
    }
    sort(node,node+caseN,compare);
    /*for(i=0;i<caseN-1;i++)//sort by y from small to big
    {
        for(j=0;j<caseN-i-1;j++)
        {
            if(node[j].y>node[j+1].y)
            {
                struct xy temp=node[j];
                node[j]=node[j+1];
                node[j+1]=temp;
            }
        }
    }
    */
    
    i=caseN-1;
    copy1[i]=node[i];
    j=caseN-1;
    while(i>=0)
    {
         
        if(node[i].x>node[j].x)
        {
            copy1[i]=node[i];
            j=i;
        }   
        i--;
    }
    /*
    for(i=0;i<caseN-1;i++)//sort by x from small to big
    {
        for(j=0;j<caseN-i-1;j++)
        {
            if(copy1[j].x>copy1[j+1].x)
            {
                struct xy temp=copy1[j];
                copy1[j]=copy1[j+1];
                copy1[j+1]=temp;
            }
        }
    }
    */
    sort(copy1,copy1+caseN,compare2);
    for(i=0;i<caseN;i++)
    {
        if(copy1[i].x>=0 && copy1[i].y>=0)
        {
            cout<<copy1[i].x<<" "<<copy1[i].y<<endl;

        }
        
        
    }
        
}

步骤：按照y值由小到大排序，从y值最大的点开始，需要明确，该点左方的点全部无效
该点右方的y值最大的点有效，然后根据此规律，即y值次最大成为最大，再找右方的次最大点。。。
最终再根据x值排序，输出即可。（自己写的排序超时）
发表于 2020-12-15 22:16:20 回复(0)
Yearss头像 Yearss 
/*
   简单，清晰 易懂
*/

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int>& p1, pair<int, int>& p2){

    if(p1.first > p2.first)
        return true;
    else if(p1.first == p2.first)
        return p1.second < p2.second;
    else
        return false;
}

vector<pair<int, int>> solve(vector<pair<int, int>>& vec){

    vector<pair<int, int>> ret;
    sort(vec.begin(), vec.end(), cmp);

    int n = vec.size();
    pair<int, int> pp = vec[0];
    for(int i = 1; i < n; i++){
        auto p = vec[i];
        if(p.first != pp.first){
            if(ret.size() == 0 || pp.second > ret.back().second){
                ret.push_back(pp);
            }
        }
        pp = vec[i];
    }

    reverse(ret.begin(), ret.end());
    return ret;

}



int main(){

    int n;
    cin >> n;
    vector<pair<int,int>> vec;
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        vec.push_back({a, b});
    }

    auto ret = solve(vec);
    for(int i = 0; i < ret.size(); i++)
        cout << ret[i].first << ' ' << ret[i].second << endl;

}

发表于 2020-11-25 19:24:45 回复(0)
好好生活是一种态度头像 好好生活是一种态度
语言：C++
通过率：100%
运行时间：349ms
内存占用：12792kb

思路总结：
  1. 先根据每个点的高度进行排序，即以及y值进行大小排序；
  2. 以最高点为参照，找到大于x_max的点的集合（此处需要更新x_max）；
  3. 然后对2步骤中找到的点集依据x进行排序，即可找到想要的结果。 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool compare_x(std::pair<int, int> p1,
              std::pair<int, int> p2) {
    return p1.first < p2.first;
}

bool compare_y(std::pair<int, int> p1,
              std::pair<int, int> p2) {
    return p1.second < p2.second;
}

int main () {
    int n;
    while (cin >> n) {
        vector<std::pair<int, int>> input_points;
        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            auto pair_ = make_pair(x, y);
            input_points.push_back(pair_);
        }
        
        // first, sort by y will find the topest
        sort(input_points.begin(), input_points.end(), compare_y);
        int x_last = input_points.back().first;
        vector<std::pair<int, int>> res_vec;
        res_vec.push_back(input_points.back());
        // find the points that x exceed the topest
        for (int i = input_points.size() - 2; i >= 0; i--) {
            if (input_points.at(i).first >= x_last) {
                res_vec.push_back(input_points.at(i));
                x_last = input_points.at(i).first;
            }
        }
        
        // then sort by x
        sort(res_vec.begin(), res_vec.end(), compare_x);
        for (int i = 0; i < res_vec.size(); i++) {
            cout << res_vec.at(i).first << " " << res_vec.at(i).second << endl;
        }
        return 0;
        
    }
}

发表于 2020-09-04 09:53:55 回复(0)
毛常松头像 毛常松 
#include <iostream>
#include <algorithm>
using namespace std;

struct Point
{
	int x;
	int y;
};
bool compare(Point a, Point b)
{
	if (a.x != b.x) return a.x > b.x;
	return a.y >= b.y;
}
Point p[500000];
Point result[500000];
int main()
{
	int count;
	cin >> count;
	for (int i  = 0; i < count; i++)
	{
		cin >> p[i].x >> p[i].y;
	}
	sort(p, p + count, compare);

	int resultIndex = 0;
	result[0] = p[0];
	for (int i = 1; i < count; i++)
	{
		if (p[i].y > result[resultIndex].y)
		{
			result[++resultIndex] = p[i];
		}
	}

	for (int i = resultIndex; i >= 0; i--)
	{
		cout << result[i].x << " " << result[i].y << endl;
	}
}

发表于 2020-08-31 11:57:33 回复(0)
牛客541472792号头像 牛客541472792号
x轴排序后，对y轴做单调队列 
#include<bits/stdc++.h>
using namespace std;
int main(){
    pair<int, int> points[500010];
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int x, y;
        cin>>x>>y;
        points[i] = make_pair(x,y);
    }
    sort(points, points+n);
    stack<int> st;
    for(int i=0;i<n;i++){
        while(!st.empty()&&points[i].second>points[st.top()].second){
            st.pop();
        }
        st.push(i);
    }
    stack<int> rev;
    while(!st.empty()){
        rev.push(st.top());
        st.pop();
    }
    while(!rev.empty()){
        int cur = rev.top();
        cout<<points[cur].first<<" "<<points[cur].second<<endl;
        rev.pop();
    }
}


发表于 2020-08-13 21:56:13 回复(0)
Tristram头像 Tristram 
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
const int N = 500010;
int main()
{
    vector<pair<int, int>> data;
    vector<pair<int, int>> res;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        data.push_back({x, y});
    }
    sort(data.begin(), data.end());
    int Y = 0;
    for (int i = n-1; i >= 0;i--)
    {
        int x = data[i].first;
        int y = data[i].second;
        if(Y>y)
        {
            continue;
        }
        else{
            Y = max(Y, y);
            res.push_back({x, y});
        }
    }
    sort(res.begin(), res.end());
    for(auto i:res)
    {
        cout << i.first << " " << i.second<< endl;
    }
        return 0;
}

发表于 2020-07-13 16:36:53 回复(1)
PandaLai头像 PandaLai
思路：先将所有点按横坐标从大到小排序，然后遍历排序后的点，若当前点的纵坐标大于等于之前已遍历点的最大纵坐标（由于已遍历点的横坐标都大于当前点，所以只需考虑纵坐标即可），则当前点满足条件。AC代码如下（PS：这题时间卡的好死，我用的python，运行时间1744ms，差点超时，而且不知为什么将纵坐标比较从大于等于改成大于就超时了，明明题目说所有点的横坐标和纵坐标都不重复的emmm）： 
n = int(raw_input())
p = []
for _ in xrange(n):
    x, y = map(int, raw_input().split())
    p.append((x, y))
p.sort(reverse=1)
res = []
max_y = float('-inf')
for i in xrange(n):
    if p[i][1] >= max_y:
        max_y = p[i][1]
        res.append(p[i])
for i in xrange(len(res)-1, -1, -1):
    print res[i][0], res[i][1]



编辑于 2020-06-21 13:51:26 回复(0)
我就是个哥哥头像 我就是个哥哥 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct point
{
    int x;
    int y;
}point;
bool compare_y(point p1,point p2)
{
    return p1.y < p2.y;
}
bool compare_x(point p1,point p2)
{
    return p1.x < p2.x;
}
int main()
{
    int n;
    cin >> n;
    vector<point> v;
    vector<point> w;
    for(int i=0;i<n;i++){
        point p;
        cin >> p.x >> p.y;
        v.push_back(p);
    }
    sort(v.begin(),v.end(),compare_y);
    int cnt=1,y_last=v.at(n-1).y,x_last=v.at(n-1).x;
    w.push_back(v.at(n-1));
    for(int i=v.size()-2;i>=0;i--){
        //cout << v.at(i).x << endl;
        if(v.at(i).x>=x_last) {
            w.push_back(v.at(i));
            x_last=v.at(i).x;
        }
    }
    sort(w.begin(),w.end(),compare_x);
    for(int i=0;i<w.size();i++)
        cout << w.at(i).x << " "<< w.at(i).y << endl;
    
    return 0;
}

发表于 2020-06-12 13:43:06 回复(1)
仿佛我的坐骑头像 仿佛我的坐骑
n=int(input())
p=[]
for i in range(n):
    x,y=map(int,input().split())
    p.append((x,y))
p=sorted(p,key=lambda x:x[0])
res=[p[-1]]
min=res[0][1]
for x in p[::-1]:
    if(x[1]>min):
        min=x[1]
        res.append(x)
for x in res[::-1]:
    print('{} {}'.format(x[0],x[1]))
如何优化?

发表于 2019-03-26 17:20:38 回复(0)
成为经典吧头像 成为经典吧 
import java.util.*;   class Point { private int x, y;  private int flag = 1;  public Point(int x, int y){ this.x = x;  this.y = y;  } public int getX() { return x;  } public void setX(int x) { this.x = x;  } public int getY() { return y;  } public void setY(int y) { this.y = y;  } public int getFlag() { return flag;  } public void setFlag(int flag) { this.flag = flag;  }
} class cmp_x implements Comparator<Point>{ public int compare(Point point1, Point point2) { return point1.getX() < point2.getX() ? 0:1;  }
} class cmp_y implements Comparator<Point>{ public int compare(Point point1, Point point2) { return point1.getY() < point2.getY() ? 0:1;  }
} public class test01 { public static void main(String[] args) {
        ArrayList<Point> points = new ArrayList<Point>();  System.out.println("plz input");  Scanner sc = new Scanner(System.in);  int N = sc.nextInt();  for (int i = 0; i < N; i ++){
            points.add(new Point(sc.nextInt(), sc.nextInt()));  } for (int j = 0; j < N; j++){ for (int k = 0; k < N; k++){
                cmp_x cmp_x = new cmp_x();  cmp_y cmp_y = new cmp_y();  if (cmp_x.compare(points.get(j), points.get(k)) +
                        cmp_y.compare(points.get(j), points.get(k)) == 0){
                    points.get(j).setFlag(0);  }
            }
        }
        Collections.sort(points, new Comparator<Point>() { public int compare(Point point1, Point point2) { return point1.getX() < point2.getX() ? 0:1;  }
        });   Iterator it = points.iterator();  while (it.hasNext()){
            Point point = (Point) it.next();  if (point.getFlag() == 1){
                System.out.print(point.getX() + " ");  System.out.println(point.getY());  }
        }
    }


}

发表于 2019-03-14 09:11:50 回复(0)
提交观点

问题信息

排序
上传者：小小
难度：
19条回答 5422浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号