人员站位的方案数 I

难度: Medium

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

我们定义 x 轴的正方向为右（x 轴递增的方向），x 轴的负方向为左（x 轴递减的方向）。类似的，我们定义 y 轴的正方向为上（y 轴递增的方向），y 轴的负方向为下（y 轴递减的方向）。

你需要安排这 n 个人的站位，这 n 个人中包括 Alice 和 Bob 。你需要确保每个点处恰好有一个人。同时，Alice 想跟 Bob 单独玩耍，所以 Alice 会以 Alice 的坐标为 左上角 ， Bob 的坐标为 右下角 建立一个矩形的围栏（注意，围栏可能不包含任何区域，也就是说围栏可能是一条线段）。如果围栏的内部或者边缘上有任何其他人，Alice 都会难过。

请你在确保 Alice 不会难过的前提下，返回 Alice 和 Bob 可以选择的点对数目。

注意，Alice 建立的围栏必须确保 Alice 的位置是矩形的左上角，Bob 的位置是矩形的右下角。比方说，以 (1, 1) ，(1, 3) ，(3, 1) 和 (3, 3) 为矩形的四个角，给定下图的两个输入，Alice 都不能建立围栏，原因如下：

图一中，Alice 在 (3, 3) 且 Bob 在 (1, 1) ，Alice 的位置不是左上角且 Bob 的位置不是右下角。
图二中，Alice 在 (1, 3) 且 Bob 在 (1, 1) ，Bob 的位置不是在围栏的右下角。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：0
解释：没有办法可以让 Alice 的围栏以 Alice 的位置为左上角且 Bob 的位置为右下角。所以我们返回 0 。

示例 2：

输入：points = [[6,2],[4,4],[2,6]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (4, 4) ，Bob 站在 (6, 2) 。
- Alice 站在 (2, 6) ，Bob 站在 (4, 4) 。
不能安排 Alice 站在 (2, 6) 且 Bob 站在 (6, 2) ，因为站在 (4, 4) 的人处于围栏内。

示例 3：

输入：points = [[3,1],[1,3],[1,1]]
输出：2
解释：总共有 2 种方案安排 Alice 和 Bob 的位置，使得 Alice 不会难过：
- Alice 站在 (1, 1) ，Bob 站在 (3, 1) 。
- Alice 站在 (1, 3) ，Bob 站在 (1, 1) 。
不能安排 Alice 站在 (1, 3) 且 Bob 站在 (3, 1) ，因为站在 (1, 1) 的人处于围栏内。
注意围栏是可以不包含任何面积的，上图中第一和第二个围栏都是合法的。

提示：

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

Submission

运行时间: 43 ms

内存: 16.0 MB

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        ans,n= 0,len(points)
        points.sort(key=lambda x:(x[0],-x[1]))
        for i,(ax,ay) in enumerate(points):
            y = -1
            for j in range(i+1,n):
                if y < points[j][1] <= ay:
                    y = points[j][1]
                    ans += 1
        return ans

Explain

此题解首先对点进行排序，排序策略是按x坐标升序排序，若x坐标相同则按y坐标降序排序。排序后，对每个点作为Alice的位置，遍历其后面的点作为Bob的位置，尝试构建一个符合条件的矩形。使用一个变量'y'来记录当前可以作为右下角的点Bob的最大y坐标，以确保不会有其他点在围栏内。通过两层循环的遍历，检查每一个可能的Alice和Bob的组合，符合条件即Alice在左上角，Bob在右下角，且围栏内没有其他点的话，则增加答案计数。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def numberOfPairs(self, points: List[List[int]]) -> int:
        ans, n = 0, len(points)  # 初始化答案和点的数量
        points.sort(key=lambda x: (x[0], -x[1]))  # 按x升序，y降序排序
        for i, (ax, ay) in enumerate(points):  # 遍历每个点作为Alice的位置
            y = -1  # 初始化y，表示无有效的Bob位置
            for j in range(i+1, n):  # 遍历可能的Bob位置
                if y < points[j][1] <= ay:  # 检查Bob是否在有效范围内
                    y = points[j][1]  # 更新y为新的Bob位置
                    ans += 1  # 符合条件，增加答案计数
        return ans  # 返回总计数

Explore

这种排序策略有两个主要目的。首先，按x坐标升序排序是为了确保当我们选择一个点作为Alice的位置时，其后的所有点都有可能作为Bob的位置，因为Bob的x坐标必须大于或等于Alice的x坐标。其次，y坐标降序排序的目的是在x坐标相同的情况下，优先考虑较高的y坐标作为Alice的位置，这样可以降低之后查找合适的Bob位置时的复杂度，因为我们只需要查找y坐标小于当前Alice y坐标的点，而不需要考虑更高的y坐标。这种排序方式有助于减少内层循环的次数，从而优化整体算法的性能。

在算法中，变量'y'用于记录在当前Alice的位置下，可以作为Bob的位置的最大y坐标。由于已经按x升序和y降序排序，当我们遍历后面的点寻找Bob的位置时，任何一个有效的Bob位置都保证了所有x坐标相同且y坐标在Alice和该Bob之间的点都已经被考虑过，因此不会成为围栏内的点。此外，对于任何x坐标大于当前Alice的点，他们的y坐标必须小于当前记录的最大y坐标'y'，以确保这些点不会位于Alice和Bob形成的矩形内部。这种策略确保了在Alice和Bob之间形成的矩形区域内不会有其他点。

在当前的算法实现中，如果Alice和Bob的坐标完全相同，即在相同的x和y坐标上，这种情况实际上是不会被计算为有效的Alice-Bob对的。这是因为算法中在内层循环时只考虑了那些y坐标严格小于Alice的y坐标的点作为Bob的候选点。因此，如果Alice和Bob坐标相同，他们不会形成一个有效的矩形（实际上也不符合题目要求的矩形定义），所以这种情况被自动排除了。如果需要处理这种情况，算法需要进行适当调整以包含这种特殊情况。