用java语言实现以下功能:P为给定的二维平面整数点集。定义 P 中某点x,如果x满足 P 中任意点都不在 x 的右上方区域内(横纵坐标都大于x),则称其为“最大的”。求出所有“最大的”点的集合.
时间: 2024-03-24 17:37:01 浏览: 90
使用java实现复数的加减乘除,并将它们存储在集合中,实现复数的增删改查等,也能按照复数的数学表示格式将集合中所有复数打印输出。
可以使用扫描线+单调栈的方法来解决这个问题。
1. 将所有点按照横坐标从小到大排序,如果横坐标相同则按照纵坐标从小到大排序。
2. 从左往右扫描每个点,用一个单调栈来保存当前最大的点。
3. 对于每个点,如果它的纵坐标比栈顶的点高,则将它入栈。
4. 如果它的纵坐标比栈顶的点低,则弹出栈顶的点,直到栈为空或者栈顶的点不在该点的右上方。
5. 最后栈中剩余的点就是所有“最大的”点的集合。
下面是Java代码实现:
```java
import java.util.*;
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class MaxPoints {
public static List<Point> findMaxPoints(Point[] points) {
Arrays.sort(points, new Comparator<Point>() {
@Override
public int compare(Point p1, Point p2) {
if (p1.x == p2.x) {
return p1.y - p2.y;
}
return p1.x - p2.x;
}
});
Stack<Point> stack = new Stack<>();
for (Point p : points) {
while (!stack.empty() && stack.peek().y < p.y) {
stack.pop();
}
stack.push(p);
}
List<Point> result = new ArrayList<>();
while (!stack.empty()) {
result.add(stack.pop());
}
return result;
}
public static void main(String[] args) {
Point[] points = new Point[] {
new Point(1, 2),
new Point(3, 1),
new Point(4, 4),
new Point(2, 3),
new Point(5, 5),
};
List<Point> maxPoints = findMaxPoints(points);
for (Point p : maxPoints) {
System.out.println(p.x + ", " + p.y);
}
}
}
```
阅读全文