j

jaryue

V1

2023/05/16阅读:14主题:默认主题

leetcode 812. 最大三角形面积

leetcode 812. 最大三角形面积.


题目描述

  1. 最大三角形面积

给你一个由 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

暴力遍历 :\

  1. 使用三重循环遍历数组中所有的三个节点的组合,
  2. 对他们分别计算面积
  3. 找出最大的面积进行返回
  • 时间复杂度(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 炫耀一下:**


分类:

后端

标签:

后端

作者介绍

j
jaryue
V1