Medium
题目描述
给你一个大小为 n x 2 的二维数组 coords，表示无限笛卡尔平面上 n 个点的坐标。
找到以 coords 中任意三个元素为顶点的三角形的最大面积的两倍，使得该三角形至少有一条边平行于 x 轴或 y 轴。形式上，如果这样的三角形的最大面积为 A，则返回 2 * A。
如果不存在这样的三角形，返回 -1。
注意三角形不能有零面积。
示例 1：
输入：coords = [[1,1],[1,2],[3,2],[3,3]]
输出：2
解释：图中显示的三角形底边为 1，高为 2。因此其面积为 1/2 * 底边 * 高 = 1。
示例 2：
输入：coords = [[1,1],[2,2],[3,3]]
输出：-1
解释：唯一可能的三角形顶点为 (1, 1), (2, 2), 和 (3, 3)。它的任何一边都不平行于 x 轴或 y 轴。
提示：
1 <= n == coords.length <= 10^51 <= coords[i][0], coords[i][1] <= 10^6- 所有
coords[i]都是唯一的
提示：
面积 * 2 = 底边 * 高- 让底边平行于 x 轴或 y 轴
- 排序以找到每个固定 x（或 y）的最大底边，然后最大高度来自另一个坐标的极值
解题思路
解题思路
这道题要求找到至少有一条边平行于坐标轴的三角形的最大面积。我们可以分两种情况考虑：
情况1：有一条边平行于x轴
当三角形有一条边平行于x轴时，这条边的两个端点具有相同的y坐标。我们可以：
- 将所有点按y坐标分组
- 对于每个y坐标，找到该水平线上最远的两个点作为底边
- 对于每个这样的底边，找到距离该水平线最远的点作为第三个顶点
情况2：有一条边平行于y轴
类似地，当三角形有一条边平行于y轴时：
- 将所有点按x坐标分组
- 对于每个x坐标，找到该竖直线上最远的两个点作为底边
- 找到距离该竖直线最远的点作为第三个顶点
优化策略
为了高效计算：
- 使用哈希表按坐标分组
- 对于每条平行线，只需要考虑最远的两个点作为底边
- 高度的计算只需要考虑距离该直线最远的点
推荐解法：使用哈希表分组 + 贪心算法，时间复杂度为O(n²)。
代码实现
class Solution {
public:
long long maxArea(vector<vector<int>>& coords) {
int n = coords.size();
if (n < 3) return -1;
long long maxArea = -1;
// Case 1: Base parallel to x-axis
unordered_map<int, vector<int>> yGroups;
for (auto& coord : coords) {
yGroups[coord[1]].push_back(coord[0]);
}
for (auto& [y, xList] : yGroups) {
if (xList.size() < 2) continue;
sort(xList.begin(), xList.end());
long long base = xList.back() - xList[0];
if (base == 0) continue;
long long maxHeight = 0;
for (auto& coord : coords) {
if (coord[1] != y) {
maxHeight = max(maxHeight, (long long)abs(coord[1] - y));
}
}
if (maxHeight > 0) {
maxArea = max(maxArea, base * maxHeight);
}
}
// Case 2: Base parallel to y-axis
unordered_map<int, vector<int>> xGroups;
for (auto& coord : coords) {
xGroups[coord[0]].push_back(coord[1]);
}
for (auto& [x, yList] : xGroups) {
if (yList.size() < 2) continue;
sort(yList.begin(), yList.end());
long long base = yList.back() - yList[0];
if (base == 0) continue;
long long maxHeight = 0;
for (auto& coord : coords) {
if (coord[0] != x) {
maxHeight = max(maxHeight, (long long)abs(coord[0] - x));
}
}
if (maxHeight > 0) {
maxArea = max(maxArea, base * maxHeight);
}
}
return maxArea;
}
};
class Solution:
def maxArea(self, coords: List[List[int]]) -> int:
n = len(coords)
if n < 3:
return -1
max_area = -1
# Case 1: Base parallel to x-axis
y_groups = {}
for x, y in coords:
if y not in y_groups:
y_groups[y] = []
y_groups[y].append(x)
for y, x_list in y_groups.items():
if len(x_list) < 2:
continue
x_list.sort()
base = x_list[-1] - x_list[0]
if base == 0:
continue
max_height = 0
for x, cy in coords:
if cy != y:
max_height = max(max_height, abs(cy - y))
if max_height > 0:
max_area = max(max_area, base * max_height)
# Case 2: Base parallel to y-axis
x_groups = {}
for x, y in coords:
if x not in x_groups:
x_groups[x] = []
x_groups[x].append(y)
for x, y_list in x_groups.items():
if len(y_list) < 2:
continue
y_list.sort()
base = y_list[-1] - y_list[0]
if base == 0:
continue
max_height = 0
for cx, y in coords:
if cx != x:
max_height = max(max_height, abs(cx - x))
if max_height > 0:
max_area = max(max_area, base * max_height)
return max_area
public class Solution {
public long MaxArea(int[][] coords) {
int n = coords.Length;
if (n < 3) return -1;
long maxArea = -1;
// Case 1: Base parallel to x-axis
var yGroups = new Dictionary<int, List<int>>();
foreach (var coord in coords) {
if (!yGroups.ContainsKey(coord[1])) {
yGroups[coord[1]] = new List<int>();
}
yGroups[coord[1]].Add(coord[0]);
}
foreach (var kvp in yGroups) {
int y = kvp.Key;
var xList = kvp.Value;
if (xList.Count < 2) continue;
xList.Sort();
long baseLength = xList[xList.Count - 1] - xList[0];
if (baseLength == 0) continue;
long maxHeight = 0;
foreach (var coord in coords) {
if (coord[1] != y) {
maxHeight = Math.Max(maxHeight, Math.Abs(coord[1] - y));
}
}
if (maxHeight > 0) {
maxArea = Math.Max(maxArea, baseLength * maxHeight);
}
}
// Case 2: Base parallel to y-axis
var xGroups = new Dictionary<int, List<int>>();
foreach (var coord in coords) {
if (!xGroups.ContainsKey(coord[0])) {
xGroups[coord[0]] = new List<int>();
}
xGroups[coord[0]].Add(coord[1]);
}
foreach (var kvp in xGroups) {
int x = kvp.Key;
var yList = kvp.Value;
if (yList.Count < 2) continue;
yList.Sort();
long baseLength = yList[yList.Count - 1] - yList[0];
if (baseLength == 0) continue;
long maxHeight = 0;
foreach (var coord in coords) {
if (coord[0] != x) {
maxHeight = Math.Max(maxHeight, Math.Abs(coord[0] - x));
}
}
if (maxHeight > 0) {
maxArea = Math.Max(maxArea, baseLength * maxHeight);
}
}
return maxArea;
}
}
var maxArea = function(coords) {
const n = coords.length;
if (n < 3) return -1;
let maxArea = 0;
// Group points by x-coordinate and y-coordinate
const xGroups = new Map();
const yGroups = new Map();
for (const [x, y] of coords) {
if (!xGroups.has(x)) xGroups.set(x, []);
if (!yGroups.has(y)) yGroups.set(y, []);
xGroups.get(x).push([x, y]);
yGroups.get(y).push([x, y]);
}
// Case 1: Two points share same x-coordinate (vertical side)
for (const points of xGroups.values()) {
if (points.length >= 2) {
for (let i = 0; i < points.length; i++) {
for (let j = i + 1; j < points.length; j++) {
const [x1, y1] = points[i];
const [x2, y2] = points[j];
const height = Math.abs(y2 - y1);
// Find third point with maximum distance from the vertical line
for (const [x3, y3] of coords) {
if (x3 !== x1) {
const base = Math.abs(x3 - x1);
const area = base * height;
maxArea = Math.max(maxArea, area);
}
}
}
}
}
}
// Case 2: Two points share same y-coordinate (horizontal side)
for (const points of yGroups.values()) {
if (points.length >= 2) {
for (let i = 0; i < points.length; i++) {
for (let j = i + 1; j < points.length; j++) {
const [x1, y1] = points[i];
const [x2, y2] = points[j];
const base = Math.abs(x2 - x1);
// Find third point with maximum distance from the horizontal line
for (const [x3, y3] of coords) {
if (y3 !== y1) {
const height = Math.abs(y3 - y1);
const area = base * height;
maxArea = Math.max(maxArea, area);
}
}
}
}
}
}
return maxArea === 0 ? -1 : maxArea;
};
复杂度分析
| 解法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 哈希表分组 | O(n²) | O(n) |
分析说明：
- 时间复杂度：O(n²) - 外层遍历每个坐标分组，内层遍历所有点找最大高度
- 空间复杂度：O(n) - 哈希表存储坐标分组信息