LeetCode 题解工作台
最小面积矩形 II
给你一个 X-Y 平面上的点数组 points ，其中 points[i] = [x i , y i ] 。 返回由这些点形成的任意矩形的最小面积，矩形的边 不一定 平行于 X 轴和 Y 轴。如果不存在这样的矩形，则返回 0 。 答案只需在 10 -5 的误差范围内即可被视作正确答案。 示例 1： …
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们用哈希表存放所有的点，然后枚举三个点 $p_1 = (x_1, y_1)$, $p_2 = (x_2, y_2)$, $p_3 = (x_3, y_3)$，其中 和 是矩形的对角线的两个端点。如果 和 构成的直线以及 和 构成的直线垂直，并且第四个点 $(x_4, y_4)=(x_2 - x_1 + x_3, y_2 - y_1 + y_3)$ 存在于哈希表中，那么就找到了一个矩形…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]。
返回由这些点形成的任意矩形的最小面积，矩形的边 不一定 平行于 X 轴和 Y 轴。如果不存在这样的矩形，则返回 0。
答案只需在10-5 的误差范围内即可被视作正确答案。
示例 1：
输入： points = [[1,2],[2,1],[1,0],[0,1]] 输出： 2.00000 解释： 最小面积矩形由 [1,2]、[2,1]、[1,0]、[0,1] 组成，其面积为 2。
示例 2：
输入： points = [[0,1],[2,1],[1,1],[1,0],[2,0]] 输出： 1.00000 解释： 最小面积矩形由 [1,0]、[1,1]、[2,1]、[2,0] 组成，其面积为 1。
示例 3：
输入： points = [[0,3],[1,2],[3,1],[1,3],[2,1]] 输出： 0 解释： 无法由这些点组成任何矩形。
提示：
1 <= points.length <= 50points[i].length == 20 <= xi, yi <= 4 * 104- 所有给定的点都是 唯一 的。
解题思路
方法一：哈希表 + 枚举
我们用哈希表存放所有的点，然后枚举三个点 , , ，其中 和 是矩形的对角线的两个端点。如果 和 构成的直线以及 和 构成的直线垂直，并且第四个点 存在于哈希表中，那么就找到了一个矩形。此时，我们可以计算出矩形的面积，并更新答案。
最后，如果找到满足条件的矩形，返回其中面积的最小值。否则，返回 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def minAreaFreeRect(self, points: List[List[int]]) -> float:
s = {(x, y) for x, y in points}
n = len(points)
ans = inf
for i in range(n):
x1, y1 = points[i]
for j in range(n):
if j != i:
x2, y2 = points[j]
for k in range(j + 1, n):
if k != i:
x3, y3 = points[k]
x4 = x2 - x1 + x3
y4 = y2 - y1 + y3
if (x4, y4) in s:
v21 = (x2 - x1, y2 - y1)
v31 = (x3 - x1, y3 - y1)
if v21[0] * v31[0] + v21[1] * v31[1] == 0:
w = sqrt(v21[0] ** 2 + v21[1] ** 2)
h = sqrt(v31[0] ** 2 + v31[1] ** 2)
ans = min(ans, w * h)
return 0 if ans == inf else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should be able to efficiently identify pairs of points that could form a rectangle.
- question_mark
Expect the candidate to consider and explain how hash tables can optimize the solution's time complexity.
- question_mark
Look for the candidate's ability to compute the area correctly and return the smallest possible value.
常见陷阱
外企场景- error
Candidates may forget to check that the points form a valid rectangle by comparing the diagonal points.
- error
Some might overlook the importance of hashing for efficient lookup and resort to inefficient brute force methods.
- error
There might be confusion regarding the precision required for floating-point answers.
进阶变体
外企场景- arrow_right_alt
Extend this problem by considering additional constraints such as large point sets or varying dimensions.
- arrow_right_alt
Modify the problem to find the largest possible rectangle instead of the smallest.
- arrow_right_alt
Introduce an additional challenge where the rectangle must be axis-aligned.