最大斜率

n个二维点 找最大斜率

1. 首先检查是否存在两个点具有相同的x坐标。如果存在，则这两点之间的斜率为无穷大，直接返回。
2. 将所有点按x坐标从小到大排序。
3. 遍历排序后的点，计算每对相邻点之间的斜率，找出最大值。

为什么排序后计算相邻的就行？

在二维平面中，给定按x坐标排序的n个点，最大斜率一定出现在相邻点之间。这是因为当存在三个有序点A(x₁,y₁)、B(x₂,y₂)、C(x₃,y₃)（x₁ < x₂ < x₃）时，若AC的斜率为k，则中间点B必然导致AB或BC的斜率至少有一个不小于k。

1.几何证明：假设AC的斜率最大，但点B的存在会破坏这一假设。若B在AC连线之上，则AB的斜率更大；若B在连线之下，则BC的斜率更大。因此，非相邻点对的斜率无法成为全局最大。

2.数学证明：假设存在非相邻点对AC的斜率最大，则根据代数推导可得出矛盾。例如：

• 若斜率AC > AB，则需满足 (y₂ - y₁)/(x₂ - x₁) < (y₃ - y₁)/(x₃ - x₁)，但这意味着点B在AC连线下方，导致BC的斜率更大。
• 反之同理，总有一个相邻点对的斜率不小于AC。

public static double findMaxSlope(int[][] points) {
        if (points.length < 2) {
            throw new IllegalArgumentException("At least two points are required");
        }

        Set<Integer> xCoords = new HashSet<>();
        for (int[] point : points) {
            int x = point[0];
            if (xCoords.contains(x)) {
                return Double.POSITIVE_INFINITY;
            }
            xCoords.add(x);
        }

        Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));

        double maxSlope = Double.NEGATIVE_INFINITY;
        for (int i = 0; i < points.length - 1; i++) {
            int[] p1 = points[i];
            int[] p2 = points[i + 1];
            int deltaY = p2[1] - p1[1];
            int deltaX = p2[0] - p1[0];
            double slope = (double) deltaY / deltaX;
            if (slope > maxSlope) {
                maxSlope = slope;
            }
        }

        return maxSlope;
    }