Hard
题目描述
在无限平面上有 n 个点。给定两个整数数组 xCoord 和 yCoord，其中 (xCoord[i], yCoord[i]) 表示第 i 个点的坐标。
你的任务是找到满足以下条件的矩形的最大面积：
- 可以用其中四个点作为矩形的角
- 矩形内部或边界上不包含任何其他点
- 矩形的边平行于坐标轴
返回你能获得的最大面积，如果无法形成这样的矩形则返回 -1。
示例 1：
输入：xCoord = [1,1,3,3], yCoord = [1,3,1,3]
输出：4
解释：我们可以用这 4 个点作为角来构成一个矩形，没有其他点在内部或边界上。因此，最大可能面积为 4。
示例 2：
输入：xCoord = [1,1,3,3,2], yCoord = [1,3,1,3,2]
输出：-1
解释：唯一可能的矩形是用点 [1,1], [1,3], [3,1] 和 [3,3]，但 [2,2] 总是在其内部。因此返回 -1。
示例 3：
输入：xCoord = [1,1,3,3,1,3], yCoord = [1,3,1,3,2,2]
输出：2
解释：最大面积矩形由点 [1,3], [1,2], [3,2], [3,3] 形成，面积为 2。
约束条件：
- 1 <= xCoord.length == yCoord.length <= 2 * 10^5
- 0 <= xCoord[i], yCoord[i] <= 8 * 10^7
- 所有给定的点都是唯一的
解题思路
这是一个复杂的几何问题，需要使用高级数据结构来高效求解。
解题思路：
预处理和分组：将所有点按 x 坐标分组，并对每组内的点按 y 坐标排序。
枚举矩形左边：对于每个 x 坐标，枚举该坐标上的任意两个点作为矩形的左边，设这两个点的 y 坐标为 y1 和 y2（y1 < y2）。
寻找右边：需要找到最近的更大 x 坐标，该坐标上恰好有且仅有两个点，其 y 坐标分别为 y1 和 y2。这样才能形成有效的矩形。
使用线段树优化：为了高效查找满足条件的最近 x 坐标，我们使用线段树来维护每个 x 坐标上在区间 [y1, y2] 内的点的数量。
验证矩形：找到候选的右边后，需要验证：
- 右边的 x 坐标上恰好有两个点在 y1 和 y2 位置
- 矩形内部和边界上没有其他点
计算面积：对于每个有效矩形，计算其面积并更新最大值。
关键优化：
- 使用坐标压缩处理大范围的坐标值
- 线段树支持区间查询，快速判断区间内点的数量
- 通过排序和二分查找提高效率
这个解法的时间复杂度为 O(n² log n)，其中 n 是点的数量。
代码实现
class Solution {
public:
long long maxRectangleArea(vector<int>& xCoord, vector<int>& yCoord) {
int n = xCoord.size();
vector<pair<int, int>> points(n);
for (int i = 0; i < n; i++) {
points[i] = {xCoord[i], yCoord[i]};
}
sort(points.begin(), points.end());
map<int, vector<int>> xToY;
for (auto& p : points) {
xToY[p.first].push_back(p.second);
}
for (auto& [x, ys] : xToY) {
sort(ys.begin(), ys.end());
}
long long maxArea = -1;
vector<int> xs;
for (auto& [x, ys] : xToY) {
xs.push_back(x);
}
for (int i = 0; i < xs.size(); i++) {
auto& ys1 = xToY[xs[i]];
for (int j = 0; j < ys1.size(); j++) {
for (int k = j + 1; k < ys1.size(); k++) {
int y1 = ys1[j], y2 = ys1[k];
for (int l = i + 1; l < xs.size(); l++) {
auto& ys2 = xToY[xs[l]];
int pos1 = lower_bound(ys2.begin(), ys2.end(), y1) - ys2.begin();
int pos2 = lower_bound(ys2.begin(), ys2.end(), y2) - ys2.begin();
if (pos1 < ys2.size() && ys2[pos1] == y1 &&
pos2 < ys2.size() && ys2[pos2] == y2) {
bool valid = true;
int count = 0;
for (int m = pos1; m <= pos2; m++) {
if (ys2[m] >= y1 && ys2[m] <= y2) {
count++;
}
}
if (count != 2) valid = false;
if (valid) {
for (auto& p : points) {
if (p.first > xs[i] && p.first < xs[l] &&
p.second >= y1 && p.second <= y2) {
valid = false;
break;
}
}
}
if (valid) {
long long area = (long long)(xs[l] - xs[i]) * (y2 - y1);
maxArea = max(maxArea, area);
break;
}
}
}
}
}
}
return maxArea;
}
};
class Solution:
def maxRectangleArea(self, xCoord: List[int], yCoord: List[int]) -> int:
from bisect import bisect_left
n = len(xCoord)
points = list(zip(xCoord, yCoord))
points.sort()
x_to_y = {}
for x, y in points:
if x not in x_to_y:
x_to_y[x] = []
x_to_y[x].append(y)
for x in x_to_y:
x_to_y[x].sort()
max_area = -1
xs = sorted(x_to_y.keys())
for i in range(len(xs)):
ys1 = x_to_y[xs[i]]
for j in range(len(ys1)):
for k in range(j + 1, len(ys1)):
y1, y2 = ys1[j], ys1[k]
for l in range(i + 1, len(xs)):
ys2 = x_to_y[xs[l]]
pos1 = bisect_left(ys2, y1)
pos2 = bisect_left(ys2, y2)
if (pos1 < len(ys2) and ys2[pos1] == y1 and
pos2 < len(ys2) and ys2[pos2] == y2):
valid = True
count = sum(1 for y in ys2 if y1 <= y <= y2)
if count != 2:
valid = False
if valid:
for x, y in points:
if xs[i] < x < xs[l] and y1 <= y <= y2:
valid = False
break
if valid:
area = (xs[l] - xs[i]) * (y2 - y1)
max_area = max(max_area, area)
break
return max_area
public class Solution {
public long MaxRectangleArea(int[] xCoord, int[] yCoord) {
int n = xCoord.Length;
var points = new List<(int x, int y)>();
for (int i = 0; i < n; i++) {
points.Add((xCoord[i], yCoord[i]));
}
points.Sort();
var xToY = new Dictionary<int, List<int>>();
foreach (var (x, y) in points) {
if (!xToY.ContainsKey(x)) {
xToY[x] = new List<int>();
}
xToY[x].Add(y);
}
foreach (var kvp in xToY) {
kvp.Value.Sort();
}
long maxArea = -1;
var xs = xToY.Keys.OrderBy(x => x).ToList();
for (int i = 0; i < xs.Count; i++) {
var ys1 = xToY[xs[i]];
for (int j = 0; j < ys1.Count; j++) {
for (int k = j + 1; k < ys1.Count; k++) {
int y1 = ys1[j], y2 = ys1[k];
for (int l = i + 1; l < xs.Count; l++) {
var ys2 = xToY[xs[l]];
int pos1 = Array.BinarySearch(ys2.ToArray(), y1);
int pos2 = Array.BinarySearch(ys2.ToArray(), y2);
if (pos1 >= 0 && pos2 >= 0) {
bool valid = true;
int count = ys2.Count(y => y >= y1 && y <= y2);
if (count != 2) valid = false;
if (valid) {
foreach (var (x, y) in points) {
if (x > xs[i] && x < xs[l] && y >= y1 && y <= y2) {
valid = false;
break;
}
}
}
if (valid) {
long area = (long)(xs[l] - xs[i]) * (y2 - y1);
maxArea = Math.Max(maxArea, area);
break;
}
}
}
}
}
}
return maxArea;
}
}
var maxRectangleArea = function(xCoord, yCoord) {
const n = xCoord.length;
const points = [];
for (let i = 0; i < n; i++) {
points.push([xCoord[i], yCoord[i]]);
}
points.sort((a, b) => a[0] - b[0]);
const xToY = new Map();
for (const [x, y] of points) {
if (!xToY.has(x)) {
xToY.set(x, []);
}
xToY.get(x).push(y);
}
for (const [x, ys] of xToY) {
ys.sort((a, b) => a - b);
}
let maxArea = -1;
const xs = Array.from(xToY.keys()).sort((a, b) => a - b);
for (let i = 0; i < xs.length; i++) {
const ys1 = xToY.get(xs[i]);
for (let j = 0; j < ys1.length; j++) {
for (let k = j + 1; k < ys1.length; k++) {
const y1 = ys1[j], y2 = ys1[k];
for (let l = i + 1; l < xs.length; l++) {
const ys2 = xToY.get(xs[l]);
const pos1 = binarySearch(ys2, y1);
const pos2 = binarySearch(ys2, y2);
if (pos1 >= 0 && pos2 >= 0) {
let valid = true;
const count = ys2.filter(y => y >= y1 && y <= y2).length;
if (count !== 2) valid = false;
if (valid) {
for (const [x, y] of points) {
if (x > xs[i] && x < xs[l] && y >= y1 && y <= y2) {
valid = false;
break;
}
}
}
if (valid) {
const area = (xs[l] - xs[i]) * (y2 - y1);
maxArea = Math.max(maxArea, area);
break;
}
}
}
}
}
}
return maxArea;
};
function binarySearch(arr, target) {
let left = 0, right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid]
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n³ log n)，其中 n 是点的数量。外层三重循环枚举左边的两个点和右边的 x 坐标，每次需要 O(log n) 的二分查找 |
相关题目
- . Minimum Area Rectangle (Medium)