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 sortedX = [...new Set(xCoord)].sort((a, b) => a - b);
const xIndex = new Map(sortedX.map((value, index) => [value, index]));
const rows = new Map();
for (let i = 0; i < n; i++) {
if (!rows.has(yCoord[i])) rows.set(yCoord[i], []);
rows.get(yCoord[i]).push(xIndex.get(xCoord[i]));
}
let size = 1;
while (size < sortedX.length) size *= 2;
const tree = new Array(size * 2).fill(-Infinity);
const update = (index, value) => {
let node = index + size;
tree[node] = value;
while (node > 1) {
node = Math.floor(node / 2);
tree[node] = Math.max(tree[node * 2], tree[node * 2 + 1]);
}
};
const queryMaximum = (left, right) => {
let result = -Infinity;
left += size;
right += size;
while (left <= right) {
if (left % 2 === 1) result = Math.max(result, tree[left++]);
if (right % 2 === 0) result = Math.max(result, tree[right--]);
left = Math.floor(left / 2);
right = Math.floor(right / 2);
}
return result;
};
const lastPairY = new Map();
let answer = -1;
const sortedRows = [...rows.entries()].sort((a, b) => a[0] - b[0]);
for (const [y, indices] of sortedRows) {
indices.sort((a, b) => a - b);
for (let i = 1; i < indices.length; i++) {
const left = indices[i - 1];
const right = indices[i];
const key = `${left},${right}`;
const bottom = lastPairY.get(key);
if (bottom !== undefined && queryMaximum(left, right) === bottom) {
const area = (sortedX[right] - sortedX[left]) * (y - bottom);
answer = Math.max(answer, area);
}
}
for (const index of indices) update(index, y);
for (let i = 1; i < indices.length; i++) {
lastPairY.set(`${indices[i - 1]},${indices[i]}`, y);
}
}
return answer;
};
复杂度分析
| 复杂度 | 分析 |
|---|---|
| 时间复杂度 | O(n³ log n)，其中 n 是点的数量。外层三重循环枚举左边的两个点和右边的 x 坐标，每次需要 O(log n) 的二分查找 |
相关题目
- 939. Minimum Area Rectangle (Medium)