leetcode 812. 最大三角形面积.

题目描述

最大三角形面积

给你一个由 X-Y 平面上的点组成的数组 points ，其中 points[i] = [xi, yi] 。从其中取任意三个不同的点组成三角形，返回能组成的最大三角形的面积。与真实值误差在 10-5 内的答案将会视为正确答案。

示例 1：

输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]] 输出：2.00000 解释：输入中的 5 个点如上图所示，红色的三角形面积最大。示例 2：

输入：points = [[1,0],[0,0],[0,1]] 输出：0.50000

提示：

3 <= points.length <= 50 -50 <= xi, yi <= 50 给出的所有点互不相同

解题思路

法1

暴力遍历 :\

使用三重循环遍历数组中所有的三个节点的组合,
对他们分别计算面积
找出最大的面积进行返回

时间复杂度(O(N^3))
空间复杂度(O(1))

执行结果

法1

该函数接收一个二维整数数组 points，表示点的坐标。然后，它使用三重循环来遍历所有可能的三个点的组合，并计算这些点组成的三角形的面积。最后，它返回能够组成的最大三角形的面积。

calculateArea 函数用于计算三个点组成的三角形的面积。它接收三个点的坐标作为参数，并使用 Shoelace 公式来计算面积。

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

    for i := 0; i < n-2; i++ {
        for j := i+1; j < n-1; j++ {
            for k := j+1; k < n; k++ {
                area := calculateArea(points[i], points[j], points[k])
                maxArea = math.Max(maxArea, area)
            }
        }
    }

    return maxArea
}
//计算面积函数
func calculateArea(p1, p2, p3 []int) float64 {
    x1, y1 := float64(p1[0]), float64(p1[1])
    x2, y2 := float64(p2[0]), float64(p2[1])
    x3, y3 := float64(p3[0]), float64(p3[1])

    return 0.5 * math.Abs(x1*(y2-y3) + x2*(y3-y1) + x3*(y1-y2))
}

**执行结果：通过显示详情查看示例代码添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户内存消耗： 2 MB , 在所有 Go 提交中击败了 89.66% 的用户通过测试用例： 57 / 57 炫耀一下:**