812. 最大三角形面积

今晚20:00直播讲「力扣入门」，直播间地址

大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

给出一些平面上点的二维坐标，求从这些点中抽取出 3 个点，能组成的最大的三角形面积。

题意很清晰。

解题方法

思路

我们把 分别向 轴投影，分别得到点。

可以得到 3 个梯形：以下图中的黄色的边为梯形的上下边，分别以三角形的三条边作为梯形的斜边。

于是得到：

我们就有了根据三角形的三点的坐标求面积的公式。

代码

三重 循环，从题目给出的二维坐标中取出 3 个点，根据上面的面积公式求组成的三角形面积。

取最大面积即可。

class Solution:
    def largestTriangleArea(self, points):
        """
        :type points: List[List[int]]
        :rtype: float
        """
        res = 0
        N = len(points)
        for i in range(N - 2):
            for j in range(i + 1, N - 1):
                for k in range(i + 2, N):
                    (x1, y1), (x2, y2), (x3, y3) = points[i], points[j], points[k]
                    res = max(res, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
        return res

复杂度

• 时间复杂度：$O(N^3)$，是给出的坐标数。
• 空间复杂度：$O(1)$，没用额外空间。

  总结

1. 求三角形的面积是两千年来的经典问题，除了死记公式以外，不妨按照我上面的做法画三条辅助线形成梯形去求。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

• 在刷题的时候，如果你不知道该怎么刷题，可以看 LeetCode 应该怎么刷？
• 如果你觉得题目太多，想在短时间内快速提高，可以看 LeetCode 最经典的 100 道题。
• 送你一份刷题的代码模板：【LeetCode】代码模板，刷题必会
• 我写的 1000 道 LeetCode 题解，都在这里了，免费拿走。