题目地址：

https://www.lintcode.com/problem/maximum-points-set/description

给定一个数组$A$，由若干长度为$2$的数组构成，每个数组代表一个平面直角坐标系的点的$x$和$y$坐标。如果某个点$(x,y)$，不存在其它点$(z,w)$使得$z>x\wedge w>y$，那么称$(x,y)$是”最大点“。要求返回所有最大点，并且返回的列表要按照$x$坐标由小到大排序。

可以先按照$x$坐标由大到小排序，排好序之后，一个点是最大点，当且仅当其$y$坐标大于等于其之后的所有点的$y$的最大值。代码如下：

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; public class Solution { /** * @param Points: a list of [x, y] * @return: return a list of points */ public List<List<Integer>> MaximumPointsSet(int[][] Points) { // write your code here List<List<Integer>> res = new ArrayList<>(); // 按x坐标由大到小排序 Arrays.sort(Points, (p1, p2) -> -Integer.compare(p1[0], p2[0])); // 记录y坐标最大值 int maxY = 0; for (int i = 0; i < Points.length; i++) { if (i == 0 || Points[i][1] >= maxY) { List<Integer> p = new ArrayList<>(Arrays.asList(Points[i][0], Points[i][1])); res.add(p); maxY = Points[i][1]; } } // 加入的顺序是x的逆序，所以要反一下序 Collections.reverse(res); return res; } }

时间复杂度$O(n\log n)$，空间$O(1)$。