LeetCode 题解工作台
找到最大三角形面积
给你一个二维数组 coords ，大小为 n x 2 ，表示一个无限笛卡尔平面上 n 个点的坐标。 找出一个 最大 三角形的 两倍 面积，其中三角形的三个顶点来自 coords 中的任意三个点，并且该三角形至少有一条边与 x 轴或 y 轴平行。严格地说，如果该三角形的最大面积为 A ，则返回 2 *…
6
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
题目要求三角形的两倍面积，因此我们可以直接计算三角形的底边和高的乘积。 又因为三角形至少有一条边与 轴或 轴平行，我们可以枚举与 轴平行的边，计算所有可能的三角形的两倍面积，然后将 横纵坐标交换后，重复上述过程，计算与 轴平行的边的所有可能的三角形的两倍面积。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个二维数组 coords，大小为 n x 2，表示一个无限笛卡尔平面上 n 个点的坐标。
找出一个 最大 三角形的 两倍 面积，其中三角形的三个顶点来自 coords 中的任意三个点，并且该三角形至少有一条边与 x 轴或 y 轴平行。严格地说，如果该三角形的最大面积为 A，则返回 2 * A。
如果不存在这样的三角形，返回 -1。
注意，三角形的面积 不能 为零。
示例 1：
输入： coords = [[1,1],[1,2],[3,2],[3,3]]
输出： 2
解释：
图中的三角形的底边为 1，高为 2。因此，它的面积为 1/2 * 底边 * 高 = 1。
示例 2：
输入： coords = [[1,1],[2,2],[3,3]]
输出： -1
解释：
唯一可能的三角形的顶点是 (1, 1)、(2, 2) 和 (3, 3)。它的任意边都不与 x 轴或 y 轴平行。
提示：
1 <= n == coords.length <= 1051 <= coords[i][0], coords[i][1] <= 106- 所有
coords[i]都是 唯一 的。
解题思路
方法一：枚举 + 哈希表
题目要求三角形的两倍面积，因此我们可以直接计算三角形的底边和高的乘积。
又因为三角形至少有一条边与 轴或 轴平行，我们可以枚举与 轴平行的边，计算所有可能的三角形的两倍面积，然后将 横纵坐标交换后，重复上述过程，计算与 轴平行的边的所有可能的三角形的两倍面积。
因此，我们设计一个函数 来计算与 轴平行的边的所有可能的三角形的两倍面积。
我们用两个哈希表 和 来记录每个横坐标对应的最小纵坐标和最大纵坐标。然后我们遍历 ，更新哈希表 和 ，同时记录横坐标的最小值和最大值。最后，我们遍历哈希表 ，计算每个横坐标对应的三角形的两倍面积，并更新答案。
在主函数中，我们先调用 函数计算与 轴平行的边的所有可能的三角形的两倍面积，然后将 横纵坐标交换后，重复上述过程，计算与 轴平行的边的所有可能的三角形的两倍面积。最后返回答案，如果答案为 0，则返回 -1。
时间复杂度 ，空间复杂度 。其中 是 的长度。
class Solution:
def maxArea(self, coords: List[List[int]]) -> int:
def calc() -> int:
mn, mx = inf, 0
f = {}
g = {}
for x, y in coords:
mn = min(mn, x)
mx = max(mx, x)
if x in f:
f[x] = min(f[x], y)
g[x] = max(g[x], y)
else:
f[x] = g[x] = y
ans = 0
for x, y in f.items():
d = g[x] - y
ans = max(ans, d * max(mx - x, x - mn))
return ans
ans = calc()
for c in coords:
c[0], c[1] = c[1], c[0]
ans = max(ans, calc())
return ans if ans else -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ability to optimize the search for valid triangles using hash lookups.
- question_mark
Understanding of geometry concepts for calculating the area of a triangle.
- question_mark
Skill in handling edge cases and ensuring the solution scales for large inputs.
常见陷阱
外企场景- error
Failing to handle cases where no valid triangle can be formed, leading to incorrect results.
- error
Using inefficient methods that result in excessive time complexity.
- error
Overlooking the need to double the area for the final output.
进阶变体
外企场景- arrow_right_alt
Allowing different coordinate systems or constraints, like a fixed boundary for the plane.
- arrow_right_alt
Considering the maximum number of points (n) for performance optimization.
- arrow_right_alt
Extending to 3D coordinates where the problem becomes more complex.