在Python中找出两个点之间不存在点且最宽的垂直区域的面积
假设我们有 n 个点 (x, y)。垂直区域是沿 y 轴无限延伸的区域。我们需要找出两个点之间不存在其他点并且是最宽的垂直区域的面积。
因此,如果输入为 pts = [[10,9],[11,11],[9,6],[11,9]],则输出为 1。
红色和蓝色区域是最优的,其内部没有点。
要解决此问题,我们将按照以下步骤操作:
- 对 pts 列表进行排序。
-
对于 i 在范围从 1 到 pts 的长度,执行以下操作:
- 返回 (pts[i, 0] – pts[i – 1, 0]) 的最大值。
示例
下面是 Python 代码实现,以获得更好的理解。
def solve(pts):
pts.sort()
return max(pts[i][0] - pts[i - 1][0] for i in range(1, len(pts)))
print(solve([[10,9],[11,11],[9,6],[11,9]]))
输入
[[10,9],[11,11],[9,6],[11,9]]
输出
1