LeetCode 题解工作台
最小面积矩形
给你一个 X-Y 平面上的点数组 points ，其中 points[i] = [x i , y i ] 。 返回由这些点形成的矩形的最小面积，矩形的边与 X 轴和 Y 轴平行。如果不存在这样的矩形，则返回 0 。 示例 1： 输入： points = [[1,1],[1,3],[3,1],[3,3…
5
题型
4
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
对于每个点，我们将其横坐标作为键，纵坐标作为值存入哈希表 中。对于哈希表中的每个键，我们将其对应的纵坐标按照从小到大的顺序排序。 然后我们从小到大枚举横坐标，对于每个横坐标，我们枚举其对应的纵坐标中的所有点对 $(y_1, y_2)$，其中 $y_1 \lt y_2$。如果我们之前已经遇到过点对 $(y_1, y_2)$，那么就可以用当前的横坐标和之前的横坐标计算出一个矩形的面积。我们用哈希表 …
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]。
返回由这些点形成的矩形的最小面积，矩形的边与 X 轴和 Y 轴平行。如果不存在这样的矩形，则返回 0。
示例 1：
输入： points = [[1,1],[1,3],[3,1],[3,3],[2,2]] 输出： 4
示例 2：
输入： points = [[1,1],[1,3],[3,1],[3,3],[4,1],[4,3]] 输出： 2
提示：
1 <= points.length <= 500points[i].length == 20 <= xi, yi <= 4 * 104- 所有给定的点都是 唯一 的。
解题思路
方法一：哈希表 + 排序 + 枚举
对于每个点，我们将其横坐标作为键，纵坐标作为值存入哈希表 中。对于哈希表中的每个键，我们将其对应的纵坐标按照从小到大的顺序排序。
然后我们从小到大枚举横坐标，对于每个横坐标，我们枚举其对应的纵坐标中的所有点对 ，其中 。如果我们之前已经遇到过点对 ，那么就可以用当前的横坐标和之前的横坐标计算出一个矩形的面积。我们用哈希表 记录每个点对 第一次出现的横坐标，这样我们就可以在常数时间内找到这个横坐标。
最后，我们返回所有矩形的面积中的最小值。
时间复杂度 ，空间复杂度 。其中 是点的数量。
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
d = defaultdict(list)
for x, y in points:
d[x].append(y)
pos = {}
ans = inf
for x in sorted(d):
ys = d[x]
ys.sort()
n = len(ys)
for i, y1 in enumerate(ys):
for y2 in ys[i + 1 :]:
if (y1, y2) in pos:
ans = min(ans, (x - pos[(y1, y2)]) * (y2 - y1))
pos[(y1, y2)] = x
return 0 if ans == inf else ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assessing the candidate's understanding of hashing and geometric properties of the points.
- question_mark
Check if the candidate efficiently handles the edge case of no valid rectangle being possible.
- question_mark
Determine if the candidate can optimize time complexity and avoid unnecessary computations.
常见陷阱
外企场景- error
Failing to correctly check for diagonal corners forming a valid rectangle.
- error
Overcomplicating the solution by not using hash lookups to speed up the search.
- error
Not considering the case where no rectangle can be formed, which should return 0.
进阶变体
外企场景- arrow_right_alt
Finding the largest area rectangle instead of the smallest.
- arrow_right_alt
Handling different sets of points with varying coordinates for efficiency.
- arrow_right_alt
Implementing the algorithm with a different data structure (e.g., sorted arrays instead of hash tables).