两点之间不包含任何点的最宽垂直区域

难度: Easy

给你 n 个二维平面上的点 points ，其中 points[i] = [x_i, y_i] ，请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。

垂直区域 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直区域 为宽度最大的一个垂直区域。

请注意，垂直区域边上的点不在区域内。

示例 1：

输入：points = [[8,7],[9,9],[7,4],[9,7]]
输出：1
解释：红色区域和蓝色区域都是最优区域。

示例 2：

输入：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
输出：3

提示：

n == points.length
2 <= n <= 10⁵
points[i].length == 2
0 <= x_i, y_i <= 10⁹

Submission

运行时间: 92 ms

内存: 47.5 MB

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        my_list = [num[0] for num in points]
        sort_list = my_list.sort()
        num_list = [(my_list[i+1]-my_list[i]) for i in range(0,len(my_list)-1)]
        return max(num_list)

Explain

题解的核心思路是首先提取出所有点的x坐标，然后对这些x坐标进行排序。排序后，相邻两点的x坐标差值就代表了这两点之间的垂直区域的宽度。题目要求的是最宽的垂直区域，因此只需要计算所有相邻x坐标的差值，并找出其中的最大值即可。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def maxWidthOfVerticalArea(self, points: List[List[int]]) -> int:
        # 提取所有点的x坐标
        my_list = [num[0] for num in points]
        # 对x坐标进行排序
        my_list.sort()
        # 计算相邻x坐标的最大差值
        num_list = [(my_list[i+1]-my_list[i]) for i in range(0, len(my_list)-1)]
        # 返回最大的差值
        return max(num_list)

Explore

在进行x坐标排序时，算法确实会遇到重复的x坐标，但这对排序结果没有影响，因为排序会保留这些重复值。在计算最宽垂直区域的宽度时，重复的x坐标意味着相邻的两点间的距离为零。因此，这些重复的x坐标会被考虑在内，但它们不会贡献任何正的宽度值，所以对于寻找最大宽度来说，重复的x坐标实际上是无效的。

Timsort是Python内置排序方法的基础，它是一种适应性、稳定的排序算法，其在最坏情况下的时间复杂度是O(n log n)，而在最佳情况下（例如，当输入已部分排序时）可以达到O(n)。对于整型数组，Timsort表现良好，因为它可以利用数组中已排序的部分来加速整个排序过程。在本题中，除非有预先知道的特殊情况使得另一种算法更适用，Timsort已经足够高效，没有必要使用特定的排序算法来替代它。

如果points数组只包含一个点，那么在提取x坐标并排序后，只会有一个x坐标值。在这种情况下，计算相邻x坐标的差值的列表将是空的，因为没有相邻的两个点。因此，尝试找出最大值时会遇到问题，因为没有元素可以比较。在实际应用中，应该在代码中添加处理这种边界情况的逻辑，例如，如果列表中的点少于两个，则可以直接返回0，因为没有垂直区域可计算。

当前的题解没有直接提供标识最宽区域在哪两个点之间的方法。不过，可以通过修改代码来实现这一功能。在计算最大差值的同时，可以记录造成这个最大差值的两个点的x坐标。具体来说，可以在计算差值的循环中添加逻辑，如果当前差值大于之前记录的最大差值，则更新最大差值，并记录这两个点的坐标。最后，除了返回最大差值，还可以返回这两个点的坐标，以标识出具体的区域。