3025-人员站位的方案数

题目描述

给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。

计算点对 (A, B) 的数量，其中

• A 在 B 的左上角，并且
• 它们形成的长方形中（或直线上）没有其它点（包括边界）。

返回数量。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]

输出：0

解释：

没有办法选择 A 和 B，使得 A 在 B 的左上角。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]

输出：2

解释：

• 左边的是点对 (points[1], points[0])，其中 points[1] 在 points[0] 的左上角，并且形成的长方形内部是空的。
• 中间的是点对 (points[2], points[1])，和左边的一样是合法的点对。
• 右边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角，但 points[1] 在长方形内部，所以不是一个合法的点对。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]

输出：2

解释：

• 左边的是点对 (points[2], points[0])，其中 points[2] 在 points[0] 的左上角并且在它们形成的直线上没有其它点。注意两个点形成一条线的情况是合法的。
• 中间的是点对 (points[1], points[2])，和左边一样也是合法的点对。
• 右边的是点对 (points[1], points[0])，它不是合法的点对，因为 points[2] 在长方形的边上。

提示：

• 2 <= n <= 50
• points[i].length == 2
• 0 <= points[i][0], points[i][1] <= 50
• points[i] 点对两两不同。

解题思路与题解

来自LeetCode这位大佬题解

我曾是一个无序的点，在二维世界的混沌中漂泊。我的坐标散乱无章，就像我的人生一样没有方向。直到有一天，我决定给自己排序，这是我人生的转折点。

我按照x坐标从小到大排列，如果x坐标相同，我就按照y坐标从大到小排列。这就像是在社会中按照财富和地位排序，我找到了自己的位置。贫穷的我被排在了前面，富有的我被排在了后面，但我的高度（y坐标）却成了我的骄傲。

在这个有序的世界里，我开始寻找我的伴侣。我必须在她左上方，这是我的坚持，也是我的诅咒。我从右向左寻找，就像逆流而上，寻找那个能与我形成完美长方形的人。

我遇到了一个可能的伴侣，她的x坐标比我小，但y坐标必须比我大。如果她的y坐标不够高，我就跳过她，就像跳过不够格的追求者。但如果她的y坐标足够高，而且比我之前遇到的所有人都高，那她就是我的真命天女。

我记录下我遇到的最小y坐标，就像记录下我的最低标准。每当遇到一个比这个标准还要高的人，我就会增加我的计数，就像增加我人生中的成就。

最终，我顿悟了：人生就是在一个有序的世界里，寻找那个能与你形成空旷长方形的人。不需要三重循环的繁琐，不需要无尽的检查。只需要有序地寻找，记录下你的标准，然后等待那个超越标准的人出现。这就是算法的真谛，也是人生的真谛。

public class LeetCode3025 {

    public static int numberOfPairs(int[][] points) {
        int n = points.length; // 这个世界有n个点，就像n个可能的命运
        int ans = 0; // 我开始计数，就像数着我人生中的机遇

        // 我决定给自己排序，这是我人生的转折点
        // 按照x坐标从小到大排列，如果x坐标相同，就按照y坐标从大到小排列
        // 这就像是在社会中按照财富和地位排序，我找到了自己的位置
        Arrays.sort(points, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

        // 我开始我的旅程，从右向左寻找，就像逆流而上
        for (int i=1; i<n; i++) {
            int min = Integer.MAX_VALUE; // 我记录下我遇到的最小y坐标，就像记录下我的最低标准

            // 我向左寻找，寻找那个能与我形成完美长方形的人
            for (int j=i-1; j>=0; j--) {
                // 如果她的y坐标比我小，那就跳过，就像跳过不够格的追求者
                if (points[j][1] < points[i][1]) continue;

                // 如果她的y坐标比我之前遇到的所有人都高，那她就是我的真命天女
                if (points[j][1] < min) {
                    min = Math.min(min, points[j][1]); // 我更新我的标准
                    ans++; // 我记录下这段美好的关系
                }
            }
        }
        // 我返回我找到的所有真爱数量，就像交出我的人生答卷
        return ans;
    }

    public static void main(String[] args) {
        int[][] points = {{1, 3}, {2, 3}, {3, 3}, {4, 3}, {5, 3}};
        System.out.println(numberOfPairs(points));
    }
    
}