LeetCode 题解工作台
用点构造面积最大的矩形 I
给你一个数组 points ，其中 points[i] = [x i , y i ] 表示无限平面上一点的坐标。 你的任务是找出满足以下条件的矩形可能的 最大 面积： 矩形的四个顶点必须是数组中的 四个 点。 矩形的内部或边界上 不能 包含任何其他点。 矩形的边与坐标轴 平行 。 返回可以获得的 最…
7
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·数学
答案摘要
我们可以枚举矩形的左下角下标 $(x_3, y_3)$ 和右上角下标 $(x_4, y_4)$，然后枚举所有的点 $(x, y)$，判断点是否在矩形的内部或边界上，如果是，说明不满足条件，否则，我们排除掉在矩形外部的点，然后判断剩下的点是否有 4 个，如果有，说明这 4 个点可以构成一个矩形，计算矩形的面积，取最大值即可。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个数组 points，其中 points[i] = [xi, yi] 表示无限平面上一点的坐标。
你的任务是找出满足以下条件的矩形可能的 最大 面积：
- 矩形的四个顶点必须是数组中的 四个 点。
- 矩形的内部或边界上 不能 包含任何其他点。
- 矩形的边与坐标轴 平行 。
返回可以获得的 最大面积 ，如果无法形成这样的矩形，则返回 -1。
示例 1：
输入： points = [[1,1],[1,3],[3,1],[3,3]]
输出：4
解释：
我们可以用这 4 个点作为顶点构成一个矩形，并且矩形内部或边界上没有其他点。因此，最大面积为 4 。
示例 2：
输入： points = [[1,1],[1,3],[3,1],[3,3],[2,2]]
输出：-1
解释：
唯一一组可能构成矩形的点为 [1,1], [1,3], [3,1] 和 [3,3]，但点 [2,2] 总是位于矩形内部。因此，返回 -1 。
示例 3：
输入： points = [[1,1],[1,3],[3,1],[3,3],[1,2],[3,2]]
输出：2
解释：
点 [1,3], [1,2], [3,2], [3,3] 可以构成面积最大的矩形，面积为 2。此外，点 [1,1], [1,2], [3,1], [3,2] 也可以构成一个符合题目要求的矩形，面积相同。
提示：
1 <= points.length <= 10points[i].length == 20 <= xi, yi <= 100- 给定的所有点都是 唯一 的。
解题思路
方法一：枚举
我们可以枚举矩形的左下角下标 和右上角下标 ，然后枚举所有的点 ，判断点是否在矩形的内部或边界上，如果是，说明不满足条件，否则，我们排除掉在矩形外部的点，然后判断剩下的点是否有 4 个，如果有，说明这 4 个点可以构成一个矩形，计算矩形的面积，取最大值即可。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def maxRectangleArea(self, points: List[List[int]]) -> int:
def check(x1: int, y1: int, x2: int, y2: int) -> bool:
cnt = 0
for x, y in points:
if x < x1 or x > x2 or y < y1 or y > y2:
continue
if (x == x1 or x == x2) and (y == y1 or y == y2):
cnt += 1
continue
return False
return cnt == 4
ans = -1
for i, (x1, y1) in enumerate(points):
for x2, y2 in points[:i]:
x3, y3 = min(x1, x2), min(y1, y2)
x4, y4 = max(x1, x2), max(y1, y2)
if check(x3, y3, x4, y4):
ans = max(ans, (x4 - x3) * (y4 - y3))
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The problem involves array manipulation and geometric reasoning.
- question_mark
Candidates should demonstrate understanding of how to leverage math for optimizations.
- question_mark
Understanding of time and space complexities when applying different solutions is crucial.
常见陷阱
外企场景- error
Incorrectly assuming that four points will always form a rectangle. The points need to align properly to form a valid rectangle.
- error
Overlooking edge cases where no rectangle can be formed, leading to an incorrect return value of 0 instead of -1.
- error
Inefficient solutions that do not make use of hashing or mathematical properties, leading to unnecessarily high time complexity.
进阶变体
外企场景- arrow_right_alt
Generalize to find rectangles of different orientations, not just axis-aligned ones.
- arrow_right_alt
Extend the problem to work with a larger set of points and optimize the algorithm for larger input sizes.
- arrow_right_alt
Modify the problem to find the minimum area instead of the maximum.