LeetCode 812. 最大三角形面积

Categories:

题目描述
思路分析
1. 解法一：枚举三点 + 叉积（推荐）
相似题目

题目描述

✅ 812. 最大三角形面积

思路分析

解法一：枚举三点 + 叉积（推荐）

核心思路：

三角形面积为 | (B - A) × (C - A) | / 2。

枚举所有三点组合，计算最大面积。

n 最大较小，三重循环可接受。

复杂度分析：

时间复杂度：O(n^3)，其中 n 表示点的数量。

空间复杂度：O(1)。

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
}

相似题目

题目	难度	考察点
223. 矩形面积	中等	几何
1037. 有效的回旋镖	简单	叉积
976. 三角形的最大周长	简单	几何
593. 有效的正方形	中等	几何
149. 直线上最多的点数	困难	几何

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/10999078