j
jaryue
V1
2023/05/16阅读:14主题:默认主题
leetcode 812. 最大三角形面积
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 炫耀一下:**
作者介绍
j
jaryue
V1