Easy

题目描述

给定在 X-Y 平面上的点数组 points，其中 points[i] = [xi, yi]，返回由任意三个不同点组成的最大三角形的面积。答案与实际答案的差值在 10^-5 内将被接受。

示例 1：

输入：points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
输出：2.00000
解释：五个点如上图所示。红色三角形是最大的。

示例 2：

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

提示：

  • 3 <= points.length <= 50
  • -50 <= xi, yi <= 50
  • 所有给定的点都是唯一的

解题思路

解题思路

这道题要求找到三个点组成的最大三角形面积。我们需要枚举所有可能的三点组合，计算每个三角形的面积，找出最大值。

核心知识点：

  1. 三角形面积公式：给定三个点 (x1,y1), (x2,y2), (x3,y3)，面积公式为： 面积 = 0.5 * |x1(y2-y3) + x2(y3-y1) + x3(y1-y2)|

  2. 这个公式也可以用向量的叉积来理解：

    • 向量 AB = (x2-x1, y2-y1)
    • 向量 AC = (x3-x1, y3-y1)
    • 面积 = 0.5 * |AB × AC| = 0.5 * |(x2-x1)(y3-y1) - (x3-x1)(y2-y1)|

算法步骤：

  1. 使用三重循环枚举所有可能的三点组合
  2. 对每个组合，使用面积公式计算三角形面积
  3. 维护最大面积值
  4. 返回结果

时间复杂度为 O(n³)，但由于题目约束 n ≤ 50，这是完全可接受的。由于只需要三重循环遍历一次，空间复杂度为 O(1)。

推荐解法： 直接枚举法，简单高效。

代码实现

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        double maxArea = 0.0;
        int n = points.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int x1 = points[i][0], y1 = points[i][1];
                    int x2 = points[j][0], y2 = points[j][1];
                    int x3 = points[k][0], y3 = points[k][1];
                    
                    double area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
                    maxArea = max(maxArea, area);
                }
            }
        }
        
        return maxArea;
    }
};

class Solution:
    def largestTriangleArea(self, points: List[List[int]]) -> float:
        max_area = 0.0
        n = len(points)
        
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    x1, y1 = points[i]
                    x2, y2 = points[j]
                    x3, y3 = points[k]
                    
                    area = 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2))
                    max_area = max(max_area, area)
        
        return max_area

public class Solution {
    public double LargestTriangleArea(int[][] points) {
        double maxArea = 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++) {
                    int x1 = points[i][0], y1 = points[i][1];
                    int x2 = points[j][0], y2 = points[j][1];
                    int x3 = points[k][0], y3 = points[k][1];
                    
                    double area = 0.5 * Math.Abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
                    maxArea = Math.Max(maxArea, area);
                }
            }
        }
        
        return maxArea;
    }
}

var largestTriangleArea = function(points) {
    let maxArea = 0.0;
    const n = points.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                const [x1, y1] = points[i];
                const [x2, y2] = points[j];
                const [x3, y3] = points[k];
                
                const area = 0.5 * Math.abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2));
                maxArea = Math.max(maxArea, area);
            }
        }
    }
    
    return maxArea;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n³)需要三重循环枚举所有三点组合
空间复杂度O(1)只使用常数级别的额外空间

相关题目