Medium
题目描述
给你一个数组 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- 所有给定的点都是唯一的。
提示：
- 如果
(x1, y1)和(x2, y2)是矩形的两个对角，那么另外两个角点是(x1, y2)和(x2, y1)。 - 固定两个点，使用集合数据结构找到另外两个点。
- 确定矩形后，遍历点数组确保没有点位于矩形的边界或内部。
解题思路
这道题要求我们找到最大面积的轴对齐矩形，且矩形内部和边界上不能有其他点。
核心思路：
枚举对角点对：由于边平行于坐标轴，我们可以枚举所有可能的对角点对
(x1,y1)和(x2,y2)，其中x1 != x2且y1 != y2。验证矩形存在性：对于每对对角点，另外两个角点必须是
(x1,y2)和(x2,y1)。我们需要验证这两个点是否在给定点集中。检查约束条件：对于每个有效的矩形，我们需要检查是否有其他点位于矩形内部或边界上。如果有，则该矩形不符合要求。
计算最大面积：在所有符合条件的矩形中，选择面积最大的。
算法步骤：
- 将所有点存储在集合中便于快速查找
- 枚举所有点对作为潜在的对角点
- 对每对对角点，检查是否能形成完整矩形
- 验证矩形内部和边界是否包含其他点
- 更新最大面积
时间复杂度为 O(n³)，其中 n 是点的数量。由于 n ≤ 10，这个复杂度是可接受的。
代码实现
class Solution {
public:
int maxRectangleArea(vector<vector<int>>& points) {
int n = points.size();
set<pair<int, int>> pointSet;
for (auto& p : points) {
pointSet.insert({p[0], p[1]});
}
int maxArea = -1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
if (x1 == x2 || y1 == y2) continue;
if (pointSet.count({x1, y2}) && pointSet.count({x2, y1})) {
bool valid = true;
int minX = min(x1, x2), maxX = max(x1, x2);
int minY = min(y1, y2), maxY = max(y1, y2);
for (auto& p : points) {
int x = p[0], y = p[1];
if ((x == x1 && y == y1) || (x == x1 && y == y2) ||
(x == x2 && y == y1) || (x == x2 && y == y2)) {
continue;
}
if (x >= minX && x <= maxX && y >= minY && y <= maxY) {
valid = false;
break;
}
}
if (valid) {
int area = abs(x2 - x1) * abs(y2 - y1);
maxArea = max(maxArea, area);
}
}
}
}
return maxArea;
}
};
class Solution:
def maxRectangleArea(self, points: List[List[int]]) -> int:
n = len(points)
point_set = set((x, y) for x, y in points)
max_area = -1
for i in range(n):
for j in range(i + 1, n):
x1, y1 = points[i]
x2, y2 = points[j]
if x1 == x2 or y1 == y2:
continue
if (x1, y2) in point_set and (x2, y1) in point_set:
valid = True
min_x, max_x = min(x1, x2), max(x1, x2)
min_y, max_y = min(y1, y2), max(y1, y2)
for x, y in points:
if (x, y) in [(x1, y1), (x1, y2), (x2, y1), (x2, y2)]:
continue
if min_x <= x <= max_x and min_y <= y <= max_y:
valid = False
break
if valid:
area = abs(x2 - x1) * abs(y2 - y1)
max_area = max(max_area, area)
return max_area
public class Solution {
public int MaxRectangleArea(int[][] points) {
int n = points.Length;
HashSet<(int, int)> pointSet = new HashSet<(int, int)>();
foreach (var p in points) {
pointSet.Add((p[0], p[1]));
}
int maxArea = -1;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int x1 = points[i][0], y1 = points[i][1];
int x2 = points[j][0], y2 = points[j][1];
if (x1 == x2 || y1 == y2) continue;
if (pointSet.Contains((x1, y2)) && pointSet.Contains((x2, y1))) {
bool valid = true;
int minX = Math.Min(x1, x2), maxX = Math.Max(x1, x2);
int minY = Math.Min(y1, y2), maxY = Math.Max(y1, y2);
foreach (var p in points) {
int x = p[0], y = p[1];
if ((x == x1 && y == y1) || (x == x1 && y == y2) ||
(x == x2 && y == y1) || (x == x2 && y == y2)) {
continue;
}
if (x >= minX && x <= maxX && y >= minY && y <= maxY) {
valid = false;
break;
}
}
if (valid) {
int area = Math.Abs(x2 - x1) * Math.Abs(y2 - y1);
maxArea = Math.Max(maxArea, area);
}
}
}
}
return maxArea;
}
}
/**
* @param {number[][]} points
* @return {number}
*/
var maxRectangleArea = function(points) {
const n = points.length;
if (n < 4) return -1;
let maxArea = -1;
// Try all combinations of 4 points
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
for (let l = k + 1; l < n; l++) {
const rect = [points[i], points[j], points[k], points[l]];
// Check if these 4 points form a valid rectangle
if (isValidRectangle(rect)) {
// Check if no other points are inside or on border
if (noPointsInside(rect, points)) {
const area = calculateArea(rect);
maxArea = Math.max(maxArea, area);
}
}
}
}
}
}
return maxArea;
};
function isValidRectangle(points) {
const xs = [...new Set(points.map(p => p[0]))].sort((a, b) => a - b);
const ys = [...new Set(points.map(p => p[1]))].sort((a, b) => a - b);
if (xs.length !== 2 || ys.length !== 2) return false;
const corners = new Set(points.map(p => `${p[0]},${p[1]}`));
return corners.has(`${xs[0]},${ys[0]}`) &&
corners.has(`${xs[0]},${ys[1]}`) &&
corners.has(`${xs[1]},${ys[0]}`) &&
corners.has(`${xs[1]},${ys[1]}`);
}
function noPointsInside(rectPoints, allPoints) {
const xs = [...new Set(rectPoints.map(p => p[0]))].sort((a, b) => a - b);
const ys = [...new Set(rectPoints.map(p => p[1]))].sort((a, b) => a - b);
const rectCorners = new Set(rectPoints.map(p => `${p[0]},${p[1]}`));
for (const point of allPoints) {
if (!rectCorners.has(`${point[0]},${point[1]}`)) {
if (point[0] >= xs[0] && point[0] <= xs[1] &&
point[1] >= ys[0] && point[1] <= ys[1]) {
return false;
}
}
}
return true;
}
function calculateArea(points) {
const xs = [...new Set(points.map(p => p[0]))].sort((a, b) => a - b);
const ys = [...new Set(points.map(p => p[1]))].sort((a, b) => a - b);
return (xs[1] - xs[0]) * (ys[1] - ys[0]);
}
复杂度分析
| 项目 | 复杂度 |
|---|---|
| 时间复杂度 | O(n³) |
| 空间复杂度 | O(n) |
其中 n 是点的数量。时间复杂度为 O(n³) 是因为我们需要枚举所有点对（O(n²)），并对每个潜在矩形检查所有其他点（O(n)）。空间复杂度为 O(n)，用于存储点集合。
相关题目
- . Minimum Area Rectangle (Medium)