Python程序：找出两点之间最宽且无其他点存在的垂直区域

假设我们得到n个点，表示为(x, y)。垂直区域是指沿y轴无限延伸的区域。我们需要找到两点之间的垂直区域，该区域内没有其他点，并且是最宽的。

例如，如果输入是 pts = [[10,9],[11,11],[9,6],[11,9]]，则输出为1。

红色和蓝色区域是最优的，并且它们内部没有点。

为了解决这个问题，我们将遵循以下步骤：

  • 对列表pts进行排序

  • 对于范围从1到pts大小的i，执行：

    • 返回(pts[i, 0] - pts[i - 1, 0]) 的最大值

示例

让我们看下面的实现来更好地理解

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

更新于：2021年10月6日

121 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告