LeetCode 812. 最大三角形面积

2024-08-01 HGNULB 约 11 分钟

文章信息 7 个分类 4 个标签

分类

题目描述

✅ 812. 最大三角形面积

题意分析

给一组平面上的点，每个点用 [x, y] 表示，要求从中任选三个点组成三角形，返回能得到的最大面积（返回浮点数，允许 $10^{-5}$ 的误差）。

题目没有要求三点不共线，也没有说一定存在面积为正的三角形——如果所有点都在一条直线上，任意三点围出的面积都是 $0$，此时答案就是 $0$。所以代码不需要为「无法构成三角形」写特殊分支，共线情形会自然算出 $0$。

最关键的信号在数据范围里：点的个数 n 在 $3$ 到 $50$ 之间，坐标是 $-50$ 到 $50$ 的整数。$n \le 50$ 意味着三元组的数量是 $\binom{50}{3} = 19600$，两万都不到——这个规模明确告诉我们暴力枚举所有三点组合就是标准答案，不需要凸包、不需要旋转卡壳，也不需要任何几何加速结构。题目难度标为「简单」也印证了这一点。

第二个信号是坐标为整数且范围很小。这意味着面积计算可以全程在整数域内进行，只在最后除以 $2$ 时才引入浮点，从根本上避开了浮点误差；同时叉积的最大绝对值约为 $100 \times 100 \times 2 = 20000$，int 完全够用，不会溢出。

边界上要覆盖：恰好三个点（只有一种组合）；所有点共线（答案是 $0$）；出现坐标为负的点（差值可能为负，必须取绝对值）；存在重复点（面积为 $0$，不影响最大值）。

解法：枚举三点 + 叉积

核心思路

既然规模允许，框架就定死为三重循环枚举所有无序三元组。真正需要想清楚的是给定三点如何算面积，以及怎么算才不引入误差。

第一个想法是套海伦公式：先算三条边长 $a, b, c$，再用 $p = \frac{a+b+c}{2}$ 和 $S = \sqrt{p(p-a)(p-b)(p-c)}$。这个做法能用，但很差：边长要开三次平方根，浮点误差会一路放大；更糟的是当三点接近共线时，$p - a$ 会是两个相近浮点数相减，发生严重的灾难性抵消，根号里甚至可能算出微小的负数导致 NaN。

第二个想法是「底乘高除以二」：选一条边当底，再求第三点到这条直线的距离当高。这同样要开方（求底边长）和做除法，误差和分支（底边长为 $0$ 时要特判）都不少。

瓶颈在于这两种做法都绕道去求了长度，而长度天然需要开方。观察一下：面积其实可以不经过长度直接得到。以点 $A$ 为原点，构造两个向量 $\vec{AB} = B - A$ 和 $\vec{AC} = C - A$，它们的叉积（二维下是一个标量）为

$\vec{AB} \times \vec{AC} = (B_x - A_x)(C_y - A_y) - (C_x - A_x)(B_y - A_y)$

这个值的绝对值恰好等于以这两个向量为邻边的平行四边形面积，而三角形是它的一半。于是面积就是 $\frac{ \vec{AB} \times \vec{AC} }{2}$，全程只有减法、乘法和一次除以 $2$，没有开方、没有除以变量、没有三角函数。

于是要维护的量极其简单：best 表示已枚举过的所有三元组中的最大面积，初值为 $0$。之所以可以放心用 $0$ 作初值而不是负无穷，是因为面积恒非负，且题目保证至少有三个点，所以 best 一定会被至少一个合法值参与比较；即使所有点共线，答案本来就该是 $0$。

叉积写法还有两个附带好处。其一，共线判定是免费的：三点共线当且仅当叉积为 $0$，不需要额外分支。其二，整数精度：由于坐标是整数，叉积也是整数，可以先在 int 域内取绝对值，最后才转成浮点除以 $2.0$，浮点运算只发生一次，误差远低于允许范围。

三重循环用 i < j < k 的写法，保证每个无序三元组只被枚举一次——顺序不同的同一组点面积相同，重复枚举只是白白多花六倍时间，不影响正确性，但没有理由这么写。

解题步骤

初始化 best = 0.0，取出 n = points.length。理由：面积恒非负，$0$ 是天然下界；题目保证 $n \ge 3$，所以不需要为「点数不足」写保护。

三重循环 i 从 $0$ 到 n-1，j 从 i+1 开始，k 从 j+1 开始。理由：严格递增的下标保证每个无序三元组恰好被枚举一次，既避免了重复计算，也天然排除了「同一个点被选两次」这种非法组合。

对每个三元组调用面积函数，若结果大于 best 就更新。理由：这是标准的打擂台，只需保留最大值，不需要记录是哪三个点。

面积函数内先算两个向量的分量：x1 = b[0] - a[0]、y1 = b[1] - a[1]、x2 = c[0] - a[0]、y2 = c[1] - a[1]。理由：把 a 当作局部原点做平移，叉积公式在平移下不变；这一步全部在整数域完成，坐标范围 $[-50, 50]$ 保证差值不超过 $100$。

计算 x1 * y2 - x2 * y1 并取绝对值。理由：这个标量是平行四边形的有向面积，符号代表 $C$ 在 $\vec{AB}$ 的哪一侧；面积要的是大小，所以取绝对值。乘积最大约 $100 \times 100 = 10^4$，两项相减不超过 $2 \times 10^4$，int 绝不会溢出。

最后除以 2.0 返回。理由：三角形是平行四边形的一半；写 2.0 而不是 2 是为了触发浮点除法——写整数 2 会做整除，把 .5 的部分截断掉。Go 里则要显式 float64(cross) / 2.0。

遍历结束返回 best。理由：所有三元组都被考察过，擂台上的就是最大值。

以 points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 走一遍。取 i=0, j=1, k=2，即 $A(0,0)$、$B(0,1)$、$C(1,0)$：x1 = 0, y1 = 1, x2 = 1, y2 = 0，叉积 $0 \times 0 - 1 \times 1 = -1$，绝对值 $1$，面积 $0.5$，best 更新为 $0.5$。取 i=0, j=1, k=3，即 $A(0,0)$、$B(0,1)$、$C(0,2)$：x1 = 0, y1 = 1, x2 = 0, y2 = 2，叉积 $0 \times 2 - 0 \times 1 = 0$，面积 $0$——三点共线被自动算成 $0$，不需要任何特判。继续枚举，当取到 i=0, j=3, k=4，即 $A(0,0)$、$B(0,2)$、$C(2,0)$：x1 = 0, y1 = 2, x2 = 2, y2 = 0，叉积 $0 \times 0 - 2 \times 2 = -4$，绝对值 $4$，面积 $2.0$，best 更新为 $2.0$。剩余组合都不超过它，最终返回 $2.0$，与期望一致。

代码实现

class Solution {
    public double largestTriangleArea(int[][] points) {
        double best = 0.0;
        int n = points.length;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    double area = area(points[i], points[j], points[k]);
                    if (area > best) {
                        best = area;
                    }
                }
            }
        }

        return best;
    }

    private double area(int[] a, int[] b, int[] c) {
        int x1 = b[0] - a[0];
        int y1 = b[1] - a[1];
        int x2 = c[0] - a[0];
        int y2 = c[1] - a[1];
        return Math.abs(x1 * y2 - x2 * y1) / 2.0;
    }
}

func largestTriangleArea(points [][]int) float64 {
    best := 0.0
    n := len(points)

    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                area := triangleArea(points[i], points[j], points[k])
                if area > best {
                    best = area
                }
            }
        }
    }

    return best
}

func triangleArea(a []int, b []int, c []int) float64 {
    x1 := b[0] - a[0]
    y1 := b[1] - a[1]
    x2 := c[0] - a[0]
    y2 := c[1] - a[1]
    cross := x1*y2 - x2*y1
    if cross < 0 {
        cross = -cross
    }
    return float64(cross) / 2.0
}

复杂度分析

时间复杂度：$O(n^3)$，其中 $n$ 是点的个数。三重循环恰好枚举 $\binom{n}{3}$ 个三元组，每个三元组内部只做四次减法、两次乘法、一次减法和一次除法，都是常数时间。$n \le 50$ 时约 $19600$ 次计算，运行时间在微秒级。

空间复杂度：$O(1)$。只维护一个 best 变量和面积函数里的四个临时整数，不排序、不建辅助结构、不递归；输入数组是只读的。

关键点总结

求二维三角形面积首选叉积：$S = \frac{ (B-A) \times (C-A) }{2}$。它只用加减乘，不开方、不除以变量、不涉及三角函数，既快又稳。海伦公式和「底乘高」都要开方，在近似共线时会有严重的精度损失，应当避免。

坐标是整数时，要尽量把计算留在整数域，只在最后一步转浮点。本题叉积全程是 int，浮点运算只有一次除以 $2.0$，误差量级远低于判题要求。这个「延迟浮点化」原则在几何题里普遍适用。

叉积的符号还额外携带方向信息：正表示逆时针、负表示顺时针、零表示共线。本题只用到绝对值，但记住符号语义能让同一个工具直接用于凸包、线段相交、点在多边形内等判定。

数据范围是选择算法的第一依据。$n \le 50$ 明确允许 $O(n^3)$，此时上凸包加旋转卡壳属于过度设计——虽然理论上更优，但代码量翻几倍且容易写错。面试中要能说清「为什么这里不需要优化」。

枚举无序组合统一用 i < j < k 的递增下标，既去重又排除自身重复选取，是所有组合枚举的默认写法。

面试视角：字节和腾讯考这题是暖场加基本功检验，考点集中在是否知道叉积和是否会因浮点写法丢分。理想作答是：先看数据范围说「$n \le 50$，$O(n^3)$ 枚举足够」，再直接给出叉积公式并说明「避免开方所以精度更好」，最后写十几行代码。如果面试官追问更优解，可以答「最大面积三角形的三个顶点一定都在凸包上，可以先求凸包再用旋转卡壳做到 $O(n \log n)$」，能说出这个结论就足够，不必现场实现。

易错点总结

错误写法：面积函数最后写成 Math.abs(x1 * y2 - x2 * y1) / 2 → 用例 points = [[0,0],[0,1],[1,0]] → 叉积绝对值是 $1$，整数除法 $1 / 2$ 得 $0$，返回 $0.0$，正确答案是 $0.5$。

错误写法：忘记对叉积取绝对值 → 用例 points = [[0,0],[0,1],[1,0]] → 叉积是 $-1$，面积算成 $-0.5$，best 永远不会被负值更新，若所有三元组都是负叉积则返回 $0$；且返回负面积本身无意义。

错误写法：三重循环写成 j 和 k 都从 $0$ 开始并只判 i != j && j != k && i != k → 用例任意输入 → 每个三元组被枚举 $6$ 次，结果虽正确但白花六倍时间；更糟的是若漏掉某个不等判断，会出现「同一个点选两次」而算出恒为 $0$ 的伪三角形。

错误写法：用海伦公式且不做数值保护 → 用例三点几乎共线如 [[0,0],[1,0],[2,0]] → $p - a$ 出现相近浮点相减，根号内可能算出极小负数，Math.sqrt 返回 NaN，NaN > best 恒为假导致该组合被静默跳过，或直接把 NaN 传出去。

错误写法：用「底乘高」且不判底边长为零 → 用例存在重复点如 [[0,0],[0,0],[1,1]] → 底边长为 $0$，求高时除以零得到 Infinity，best 被污染成无穷大。

错误写法：best 初值设成 Double.MIN_VALUE 或 $-1$ → 用例所有点共线如 [[0,0],[1,1],[2,2]] → 所有面积都是 $0$，若初值是 $-1$ 会正确更新到 $0$；但若把更新条件写成 >= 之外还额外要求 area > 0 就会返回 $-1$，正确答案是 $0$。注意 Double.MIN_VALUE 其实是最小的正数而非负无穷，这是 Java 里的经典陷阱。

错误写法：叉积写成 x1 * y2 + x2 * y1 或 x1 * x2 - y1 * y2 → 用例 [[0,0],[0,1],[1,0]] → 前者得 $0 \times 0 + 1 \times 1 = 1$ 侥幸相同，但换成 [[0,0],[1,2],[3,1]] 时前者得 $1 \times 1 + 3 \times 2 = 7$ 而正确叉积是 $1 \times 1 - 3 \times 2 = -5$，面积算成 $3.5$ 而非 $2.5$。

错误写法：向量构造时基点不统一，写成 x1 = b[0] - a[0] 但 x2 = c[0] - b[0] → 用例 [[0,0],[0,2],[2,0]] → 两个向量不再共享同一个顶点，叉积算出的是另一个平行四边形的面积，结果偏离。

错误写法：Go 里 cross 声明成 float64 并直接用 math.Abs → 用例任意输入 → 结果正确但把本可保持整数精度的中间量提前浮点化，在坐标范围更大的变体题里会累积误差；更常见的连带错误是忘记 float64(cross) 转换导致编译失败。

错误写法：认为「面积最大的三角形一定包含距离最远的两个点」，于是先求最远点对再枚举第三点 → 用例 [[0,0],[0,10],[10,0],[5,5]] → 最远点对是 $(0,10)$ 与 $(10,0)$，配任意第三点的最大面积是 $25$；但 $(0,0)$、$(0,10)$、$(10,0)$ 的面积是 $50$，该点对并非最远点对，结论不成立。

相似题目

题目	难度	考察点
149. 直线上最多的点数	困难	同样靠叉积判共线，但要按斜率分组计数，需处理重复点与整数化斜率
976. 三角形的最大周长	简单	输入是边长而非坐标，靠排序加三角不等式贪心，不涉及任何几何计算
593. 有效的正方形	中等	四点判形状，用距离平方的多重集合避免开方，同样体现「留在整数域」原则
223. 矩形面积	中等	求两个轴对齐矩形的并面积，考察重叠区间的容斥而非三角形几何
1401. 圆和矩形是否有重叠	中等	用距离平方与半径平方比较来避免开方，是精度友好写法的另一个典型