求最大平行轴三角形面积
2025年7月1日大约 18 分钟
求最大平行轴三角形面积
USER
给你一个二维数组 coords，大小为 n x 2，表示一个无限笛卡尔平面上 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^5
1 <= coords[i][0], coords[i][1] <= 10^6
所有 coords[i] 都是 唯一 的。
``java
class Solution {
public long maxArea(int[][] coords) {
}
}
``ASSISTANT
已深度思考(用时 2 分 49 秒)
我们需要找到最大三角形的两倍面积，且三角形至少有一条边与 x 轴或 y 轴平行。
注意：题目要求返回 2 倍面积，所以我们在计算面积时，可以直接计算 2 倍面积，避免小数。
三角形至少有一条边与坐标轴平行，那么我们可以考虑两种情况：
1. 有一条边与 x 轴平行（即这条边上的两个点的 y 坐标相同）
2. 有一条边与 y 轴平行（即这条边上的两个点的 x 坐标相同）
但是，有可能同一个三角形同时满足两种情况（即一条边与 x 轴平行，另一条与 y 轴平行），但这种情况我们会在两种情况的考虑中都会覆盖。
思路：
我们可以分别考虑这两种情况，然后取最大值。
情况 1：有一条边与 x 轴平行。
假设这条边由两个点 A(x1, y)和 B(x2, y)组成，则底边长度为 |x2 - x1|。
我们需要第三个点 C(x3, y3)，那么三角形的高就是 |y3 - y|。
那么三角形的面积（的 2 倍）为：底 _ 高 = |x2 - x1| _ |y3 - y| （注意这里已经是 2 倍面积了，因为三角形面积公式是 1/2*底*高，而 2 倍面积就是底\*高）
所以，对于固定的 y（即同一行的点），我们想要最大化底边，即取同一行中 x 坐标的最小值和最大值，这样底边就是最大（max_x - min_x）。
然后，对于这个 y，我们还需要一个不在这一行上的点（即 y3 != y），并且|y3-y|尽可能大。但注意，y3 可以取其他任意点。
因此，我们可以： - 首先按 y 坐标分组，记录每个 y 对应的 x 的最大值和最小值（因为底边由最小 x 和最大 x 决定）。 - 同时，记录整个点集的最小 x、最大 x、最小 y、最大 y（因为高的最大值只与 y 的极值有关，即最大高是 max_y-min_y，但注意这个高可能不是当前 y 对应的，所以我们需要整个点集的 y 范围）。
但是，对于固定的 y，我们只能使用其他 y 坐标的点，所以高的最大值实际上可以是 max(|max_y - y|, |min_y - y|)。
因此，对于每个 y，其对应的最大底边为 (max_x_in_y - min_x_in_y)，最大高为 max(y - min_y_all, max_y_all - y) （这里 min_y_all 和 max_y_all 是所有点的最小 y 和最大 y）。
那么该 y 对应的最大面积（两倍）为 (max_x_in_y - min_x_in_y) \* max(y - min_y_all, max_y_all - y)
注意：这里的高是相对于该行的任意一个点，而我们需要第三个点。但是，由于我们取整个点集的最大 y 和最小 y，那么肯定存在一个 y 坐标等于 min_y_all 或 max_y_all 的点，所以这个高是可以达到的。
情况 2：有一条边与 y 轴平行。
同理，假设边由两个点 A(y1,x)和 B(y2,x)组成，这里 x 相同，y 不同。实际上，我们按 x 分组，底边长度为 |y2-y1|，高为 |x3 - x|。
同样，对于每个 x，底边最大值为 (max_y_in_x - min_y_in_x)，高为 max(x - min_x_all, max_x_all - x)。
那么该 x 对应的最大面积（两倍）为 (max_y_in_x - min_y_in_x) \* max(x - min_x_all, max_x_all - x)
然后，我们取两种情况下的最大值。
但是，需要注意的是：同一个三角形可能同时满足两种情况，但我们分别计算，取最大值并不会影响结果，因为我们要求的是最大三角形。
然而，我们是否可能遗漏没有边与坐标轴平行的三角形？题目要求至少有一条边与坐标轴平行，所以我们只考虑这两种情况。
步骤：
1. 预处理：找出所有点的最小 x、最大 x、最小 y、最大 y。
2. 分组：
Map<Integer, int[]> groupX = new HashMap<>();
// 对于情况 1，按 y 分组，我们记录每个 y 对应的最小 x 和最大 x。
// 同样，对于情况 2，按 x 分组，记录每个 x 对应的最小 y 和最大 y。
3. 遍历所有点，进行分组：
for (int[] point : coords) {
int x = point[0], y = point[1];
// 按 y 分组：更新 y 对应的最小 x 和最大 x
// 按 x 分组：更新 x 对应的最小 y 和最大 y
}
4. 计算情况 1 的最大值：
long ans = -1;
for (Map.Entry<Integer, int[]> entry : groupY.entrySet()) { // 注意：这里 entry 的 key 是 y，value 是一个数组[minX, maxX]
int yVal = entry.getKey();
int[] xs = entry.getValue();
long base = xs[1] - xs[0]; // 底边，即 maxX - minX
// 高：取当前 yVal 到整个点集 y 的极值的最小值？不对，高应该是当前 yVal 到极值 y 的最大差值
long height = Math.max((long)yVal - minY, (long)maxY - yVal);
long area = base \* height;
if (area > ans) {
ans = area;
}
}
5. 计算情况 2 的最大值：
for (Map.Entry<Integer, int[]> entry : groupX.entrySet()) { // 这里 key 是 x，value 是[minY, maxY]
int xVal = entry.getKey();
int[] ys = entry.getValue();
long base = ys[1] - ys[0]; // 底边，即 maxY-minY
long height = Math.max((long)xVal - minX, (long)maxX - xVal);
long area = base \* height;
if (area > ans) {
ans = area;
}
}
6. 如果 ans 大于 0，返回 ans；否则返回-1。
但是注意：有可能找不到任何三角形？比如所有点共线（斜的）？但题目要求三角形面积不能为零。不过我们在分组时，同一个 y 分组的点至少有两个不同的 x（否则 maxX-minX=0，面积也为 0），同理同一个 x 分组的点至少有两个不同的 y。所以，我们考虑每个分组时，如果某个组只有一个点，那么 base 为 0，面积为 0。另外，如果整个点集只有一个 y 值（即所有点都在一条水平线上），那么情况 1 中每个分组（只有一个 y 值）的高就是 0（因为 minY=maxY，那么 minY_all = maxY_all，所以 height=0）；同理，如果所有点都在一条竖直线上，情况 2 的高也是 0。所以，如果整个点集共线（无论是水平、竖直还是斜的），我们得到的最大面积将为 0？但注意： - 斜的共线：那么情况 1 和情况 2 都不会有非零的底和高？因为情况 1 要求同 y 的点，但斜线上不可能有同 y 的两个点（除非全在同一水平，但又不是水平共线）？所以实际上，在斜线共线时，情况 1 和情况 2 都得不到非零面积，所以 ans 为 0，但题目要求三角形面积不能为零，且如果不存在这样的三角形则返回-1。
因此，我们在最后需要判断：如果 ans==0，那么返回-1 吗？但是，有可能存在非零面积但 ans 被更新为大于 0 的值。所以，我们初始值设为-1，然后如果有更新就更新为更大的值。如果没有任何更新，那么 ans 仍然是-1。
但是，注意：有可能存在三角形，但它的最大面积对应的底边和高可能出现在不同的分组？比如，情况 1 中，同一个 y 分组，我们取 minX 和 maxX 作为底边，然后取一个在 minY 的点作为第三个点（这样高就是 y-minY）。但是，如果我们同一个 y 分组只有一个点，那么 base=0，则面积为 0，所以我们跳过这种情况。所以，我们在分组时，对于只有一个点的分组，可以忽略（因为 base=0，面积为 0，不会更新最大值）。但是，在分组时，我们每个分组至少需要两个点才能形成一条边（底边）。因此，我们在分组时，可以只考虑有至少两个点的分组吗？不过，题目要求底边必须由两个点组成，第三个点需要另外取。所以，我们分组时，如果某个 y 值只有一个点，那么该组不能形成底边，所以我们可以不处理或者处理时面积为 0，不影响。
但是，我们分组时，同一个分组（同一个 y）需要记录最小 x 和最大 x，如果只有一个点，那么 minX 和 maxX 相等，差值为 0，面积为 0。
另外，注意高：如果整个点集只有一个 y 值，那么 minY==maxY，那么高为 0，面积为 0。
所以，我们不需要特别处理只有一个点的分组，因为面积为 0，不会更新最大值。
但是，还有一个问题：第三个点必须存在吗？当我们计算高的时候，我们假设存在一个 y 坐标为 minY_all 的点，但确实存在吗？是的，因为我们取的是整个点集的最小 y 和最大 y，所以一定存在这样的点。因此，高的计算是可靠的。
然而，有可能在情况 1 中，同一个 y 分组的点只有两个，但是第三个点我们取到了整个点集的极值 y 的点，这样是合法的。
但是，还有没有可能一个三角形同时被计算两次？比如，三角形有两条边分别平行于 x 轴和 y 轴（即直角三角形），这种情况会被情况 1 和情况 2 都计算一次吗？
假设三角形三个点：A(x1,y1), B(x1,y2), C(x2,y1)。那么：
在情况 1 中，我们可以取平行于 x 轴的边：A(x1,y1)和 C(x2,y1)，则底边是|x2-x1|，高是|y2-y1|（取 B 点）。
在情况 2 中，我们可以取平行于 y 轴的边：A(x1,y1)和 B(x1,y2)，则底边是|y2-y1|，高是|x2-x1|。
所以，两种情况计算出的面积是相同的，都是 |x2-x1|\*|y2-y1|。所以会被计算两次，但没关系，我们取最大值。
因此，代码步骤：
1. 初始化整个点集的最小x、最大x、最小y、最大y。
long minX = Long.MAX_VALUE, maxX = Long.MIN_VALUE;
long minY = Long.MAX_VALUE, maxY = Long.MIN_VALUE;
2. 分组：
Map<Integer, Integer> minXByY = new HashMap<>();
Map<Integer, Integer> maxXByY = new HashMap<>();
Map<Integer, Integer> minYByX = new HashMap<>();
Map<Integer, Integer> maxYByX = new HashMap<>();
注意：坐标范围是1到10^6，所以可以用int。
for (int[] p : coords) {
int x = p[0], y = p[1];
// 更新全局变量
minX = Math.min(minX, x);
maxX = Math.max(maxX, x);
minY = Math.min(minY, y);
maxY = Math.max(maxY, y);
// 按y分组更新x
minXByY.put(y, Math.min(minXByY.getOrDefault(y, Integer.MAX_VALUE), x));
maxXByY.put(y, Math.max(maxXByY.getOrDefault(y, Integer.MIN_VALUE), x));
// 按x分组更新y
minYByX.put(x, Math.min(minYByX.getOrDefault(x, Integer.MAX_VALUE), y));
maxYByX.put(x, Math.max(maxYByX.getOrDefault(x, Integer.MIN_VALUE), y));
}
3. 初始化答案：long maxArea2 = -1; // 2倍面积的最大值
4. 处理情况1：遍历每个y（在minXByY中的keySet，或者maxXByY的keySet，两者一样）
for (int y : minXByY.keySet()) {
int minXForY = minXByY.get(y);
int maxXForY = maxXByY.get(y);
long base = maxXForY - minXForY; // 底边长度
if (base <= 0) continue; // 实际上base至少0，等于0时面积为0，不更新也可以
long height = Math.max(y - minY, maxY - y); // 高
if (height <= 0) continue; // 如果高为0，则面积为0
long area2 = base * height;
if (area2 > maxArea2) {
maxArea2 = area2;
}
}
5. 处理情况2：遍历每个x（在minYByX的keySet）
for (int x : minYByX.keySet()) {
int minYForX = minYByX.get(x);
int maxYForX = maxYByX.get(x);
long base = maxYForX - minYForX; // 底边长度
if (base <= 0) continue;
long height = Math.max(x - minX, maxX - x); // 高
if (height <= 0) continue;
long area2 = base * height;
if (area2 > maxArea2) {
maxArea2 = area2;
}
}
6. 如果maxArea2为-1，则返回-1。但是，有可能maxArea2被更新过，也可能没有。注意：我们初始化为-1，如果没有任何情况更新（即没有找到有效三角形），那么返回-1。
但是，有可能底边为 0，或者高为 0 的情况，我们跳过了，所以如果没有满足条件的三角形，maxArea2 还是-1。
然而，还有一个问题：我们是否有可能漏掉三角形？
假设：在情况 1 中，同一个 y 值上有多个点，我们取该 y 值的最小 x 和最大 x，这样确保底边最长。然后第三个点取整个点集中 y 坐标最小或最大的点，这样确保高最大。因此，对于每个 y 值，我们只考虑底边取该 y 值的最远两个点，高取极值点，这是正确的，因为三角形面积在底边固定时，高取最远的点会得到最大面积。
但是，有没有可能第三个点并不是整个点集的极值点，但同样满足条件？不是，因为我们要最大化面积，底边固定时，高越大越好，所以取极值点一定是最大的。
所以，这个算法是合理的。
注意：由于坐标范围较大，我们使用 long 来存储面积，避免溢出。
但是，在分组时，同一个 y 值，我们只存储了最小 x 和最大 x，如果这个 y 值上有很多点，我们只记录两个点（最小和最大），这样忽略了一些点，但是第三个点我们并没有从同一 y 值上取，而是从其他 y 值上取，所以没问题。
测试示例 1：[[1,1],[1,2],[3,2],[3,3]]
点：(1,1), (1,2), (3,2), (3,3)
情况 1：按 y 分组
y=1: minX=1, maxX=1 -> base=0 （跳过）
y=2: minX=1, maxX=3 -> base=2; 高：minY=1, maxY=3 -> height = max(2-1, 3-2)=max(1,1)=1 -> area2=2
y=3: minX=3, maxX=3 -> base=0 （跳过）
情况 2：按 x 分组
x=1: minY=1, maxY=2 -> base=1; 高：minX=1, maxX=3 -> height = max(1-1,3-1)=max(0,2)=2 -> area2=2
x=3: minY=2, maxY=3 -> base=1; 高：max(3-1,3-3)？其实是 max(3-1, 3-3)=2 -> area2=2
所以最大值为 2，正确。
示例 2：[[1,1],[2,2],[3,3]]
情况 1：按 y 分组：
y=1: minX=1, maxX=1 -> base=0
y=2: minX=2, maxX=2 -> base=0
y=3: minX=3, maxX=3 -> base=0
情况 2：按 x 分组：
x=1: minY=1, maxY=1 -> base=0
x=2: base=0
x=3: base=0
所以 maxArea2 还是初始值-1，返回-1。
但是，考虑一个例子：[[1,1],[2,1],[1,2]]，这是一个直角三角形。
情况 1：y=1: minX=1, maxX=2 -> base=1; 高：整个点集的 y：minY=1, maxY=2 -> height=max(1-1=0, 2-1=1) -> height=1 -> area2=1
情况 2：x=1: minY=1, maxY=2 -> base=1; 高：整个点集的 x：minX=1, maxX=2 -> height=max(1-1=0,2-1=1) -> height=1 -> area2=1
所以答案返回 1。
但是，注意，在示例 1 中，我们有可能在情况 1 的 y=2 分组中，使用点(1,2)和(3,2)形成底边，然后第三个点取(1,1)或(3,3)都可以。但是我们计算高时使用了整个点集的极值 y，这没有问题，因为点(1,1)的 y=1（是最小 y）和点(3,3)的 y=3（是最大 y），所以我们计算高时取的是最大值，也就是 1（因为对于 y=2，高=1 或 1，取最大 1）。而底边为 2，所以面积 2 倍为 2。在情况 2 中，x=1 分组有 y=1 和 y=2，但是底边=1（y 从 1 到 2），高=2（因为整个点集 x 从 1 到 3，所以 x=1 的高是 max(1-1,3-1)=2），所以面积 2 倍=2。所以两种情况都得到 2。
因此，代码实现如下。
但是，注意：在分组时，我们只需要同一个分组的最小值和最大值，所以不需要存储所有点。
另外，时间复杂度：O(n)，因为遍历点进行分组，然后分组后遍历分组（分组数最大为 n，因为每个点可能在不同的分组，但同一个 x 或 y 的分组我们只记录最小最大，所以分组数最多 n，也就是点的个数）。
但是，n 最大 10^5，所以没有问题。
让我们写代码。
注意：全局的最小 x、最大 x 等，要在遍历所有点的时候更新。
代码：为了解决这个问题，我们需要找出一个最大三角形的两倍面积，该三角形的三个顶点来自给定的坐标点，并且至少有一条边与 x 轴或 y 轴平行。以下是详细的解决思路和代码实现：
解决思路
- 问题分析：给定一组坐标点，我们需要构造一个三角形，其至少有一条边平行于 x 轴或 y 轴。三角形面积的两倍的计算公式为底边长乘以高，其中底边是平行于坐标轴的边的长度，高是第三个顶点到底边的垂直距离。
- 关键观察：
- 若有一条边平行于 x 轴，则该边上两点的 y 坐标相同，底边为两点间 x 坐标的差值，高为第三点 y 坐标与该边 y 坐标的绝对差的最大值（使用整个点集的 y 坐标极值）。
- 若有一条边平行于 y 轴，则该边上两点的 x 坐标相同，底边为两点间 y 坐标的差值，高为第三点 x 坐标与该边 x 坐标的绝对差的最大值（使用整个点集的 x 坐标极值）。
- 算法选择：
- 首先，遍历所有点，记录整个点集的最小和最大 x、y 坐标。
- 然后，按 y 坐标分组记录每个 y 对应的最小和最大 x 坐标（用于平行于 x 轴的边）。
- 同样，按 x 坐标分组记录每个 x 对应的最小和最大 y 坐标（用于平行于 y 轴的边）。
- 分别计算两种情况下的最大面积（底边乘以高），并取两者的最大值作为结果。
- 边界情况：若没有满足条件的三角形（如所有点共线），则返回-1。
代码实现
import java.util.*;
class Solution {
public long maxArea(int[][] coords) {
if (coords == null || coords.length < 3) return -1;
long minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
long minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
Map<Integer, Integer> minXForY = new HashMap<>();
Map<Integer, Integer> maxXForY = new HashMap<>();
Map<Integer, Integer> minYForX = new HashMap<>();
Map<Integer, Integer> maxYForX = new HashMap<>();
// 遍历所有点，初始化全局最小/最大坐标和分组信息
for (int[] p : coords) {
int x = p[0];
int y = p[1];
// 更新全局最小和最大坐标
if (x < minX) minX = x;
if (x > maxX) maxX = x;
if (y < minY) minY = y;
if (y > maxY) maxY = y;
// 更新按y分组的最小和最大x坐标
minXForY.put(y, Math.min(minXForY.getOrDefault(y, Integer.MAX_VALUE), x));
maxXForY.put(y, Math.max(maxXForY.getOrDefault(y, Integer.MIN_VALUE), x));
// 更新按x分组的最小和最大y坐标
minYForX.put(x, Math.min(minYForX.getOrDefault(x, Integer.MAX_VALUE), y));
maxYForX.put(x, Math.max(maxYForX.getOrDefault(x, Integer.MIN_VALUE), y));
}
long maxArea2 = -1; // 初始值，表示无有效三角形
// 处理平行于x轴的边的情况
for (Map.Entry<Integer, Integer> entry : minXForY.entrySet()) {
int y = entry.getKey();
int minXInY = entry.getValue();
int maxXInY = maxXForY.get(y);
long base = maxXInY - minXInY;
if (base <= 0) continue; // 底边长度无效
long height = Math.max(y - minY, maxY - y);
if (height <= 0) continue; // 高无效
long area2 = base * height;
if (area2 > maxArea2) {
maxArea2 = area2;
}
}
// 处理平行于y轴的边的情况
for (Map.Entry<Integer, Integer> entry : minYForX.entrySet()) {
int x = entry.getKey();
int minYInX = entry.getValue();
int maxYInX = maxYForX.get(x);
long base = maxYInX - minYInX;
if (base <= 0) continue; // 底边长度无效
long height = Math.max(x - minX, maxX - x);
if (height <= 0) continue; // 高无效
long area2 = base * height;
if (area2 > maxArea2) {
maxArea2 = area2;
}
}
return maxArea2 == -1 ? -1 : maxArea2;
}
}代码说明
- 初始化：设置全局最小和最大 x、y 坐标的初始值，并初始化四个映射表分别存储按 y 分组的最小和最大 x 坐标、按 x 分组的最小和最大 y 坐标。
- 遍历点集：更新全局最小和最大坐标，同时更新分组信息中的最小和最大坐标值。
- 处理平行于 x 轴的边：
- 对于每个 y 坐标，计算该组点的最小和最大 x 坐标的差值作为底边长。
- 计算该 y 坐标到整个点集最小 y 和最大 y 坐标的最大差值作为高。
- 计算两倍面积（底边乘以高）并更新最大面积值。
- 处理平行于 y 轴的边：类似地，计算底边长和高，更新最大面积值。
- 返回结果：若存在满足条件的三角形，返回最大面积的两倍；否则返回-1。
此算法高效处理了问题，时间复杂度为 O(n)，空间复杂度为 O(n)，适用于大型点集。