LeetCode 题解工作台
人员站位的方案数 II
给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [x i , y i ] 。 我们定义 x 轴的正方向为 右 （ x 轴递增的方向 ），x 轴的负方向为 左 （ x 轴递减的方向 ）。类似的，我们定义 y 轴的正方向为 上 （ y 轴递增…
5
题型
7
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
我们不妨考虑枚举矩形左上角的点 $(x_1, y_1)$，那么根据题目，右下角的点 $(x_2, y_2)$ 随着 的增大，纵坐标 也会要严格增大，才符合题意。 因此，我们对所有点按照 坐标升序排序，如果 坐标相同，按照 坐标降序排序。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个 n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。
我们定义 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 <= 1000points[i].length == 2-109 <= points[i][0], points[i][1] <= 109points[i]点对两两不同。
解题思路
方法一：排序 + 枚举
我们不妨考虑枚举矩形左上角的点 ，那么根据题目，右下角的点 随着 的增大，纵坐标 也会要严格增大，才符合题意。
因此，我们对所有点按照 坐标升序排序，如果 坐标相同，按照 坐标降序排序。
然后我们枚举左上角的点 ，并且维护一个最大的 ，记为 ，表示所有右下角的点的纵坐标的最大值。然后我们枚举右下角的点 ，如果 大于 并且小于等于 ，那么我们就找到了一个合法的方案，将答案加一，然后更新 为 。
枚举完所有的点对后，我们就得到了答案。
时间复杂度 ，空间复杂度 。其中 是点的数量。
class Solution:
def numberOfPairs(self, points: List[List[int]]) -> int:
points.sort(key=lambda x: (x[0], -x[1]))
ans = 0
for i, (_, y1) in enumerate(points):
max_y = -inf
for _, y2 in points[i + 1 :]:
if max_y < y2 <= y1:
max_y = y2
ans += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Sorting points cleverly can simplify fence validation.
- question_mark
Consider degenerate rectangles where fence area is zero.
- question_mark
Be mindful of off-by-one errors when checking if points lie on the fence.
常见陷阱
外企场景- error
Forgetting that the fence can be a line, not just a rectangle with area.
- error
Checking all permutations instead of efficient pair-based counting.
- error
Incorrectly including points exactly on the fence as invalid.
进阶变体
外企场景- arrow_right_alt
Allow multiple people inside the fence and count ways with k extra people.
- arrow_right_alt
Change the fence shape from rectangle to arbitrary convex polygon.
- arrow_right_alt
Limit Alice and Bob placements to a specific quadrant and count arrangements.