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

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

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

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

示例 1：

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/10/31/points3.png)​

**输入：** 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 <= 105
• points[i].length == 2
• 0 <= xi, yi <= 109

方法一：排序

思路

两点之间内部不包含任何点的最宽垂直面积的宽度，即所有点投影到横轴上后，求相邻的两个点的最大距离。可以先将输入的坐标按照横坐标排序，然后依次求出所有相邻点的横坐标距离，返回最大值。

代码

[sol1-Python3]

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

[sol1-Java]

class Solution {
    public int maxWidthOfVerticalArea(int[][] points) {
        Arrays.sort(points, (a, b) -> a[0] - b[0]);
        int mx = 0;
        for (int i = 1; i < points.length; i++) {
            mx = Math.max(points[i][0] - points[i - 1][0], mx);
        }
        return mx;
    }
}

[sol1-C#]

public class Solution {
    public int MaxWidthOfVerticalArea(int[][] points) {
        Array.Sort(points, (a, b) => a[0] - b[0]);
        int mx = 0;
        for (int i = 1; i < points.Length; i++) {
            mx = Math.Max(points[i][0] - points[i - 1][0], mx);
        }
        return mx;
    }
}

[sol1-C++]

class Solution {
public:
    int maxWidthOfVerticalArea(vector<vector<int>>& points) {
        sort(points.begin(), points.end());
        int mx = 0;
        for (int i = 1; i < points.size(); i++) {
            mx = max(points[i][0] - points[i - 1][0], mx);
        }
        return mx;
    }
};

[sol1-C]

#define MAX(a, b) ((a) > (b) ? (a) : (b))

static int cmp(const void *pa, const void *pb) {
    return (*(int **)pa)[0] - (*(int **)pb)[0];
}

int maxWidthOfVerticalArea(int** points, int pointsSize, int* pointsColSize) {
    qsort(points, pointsSize, sizeof(int *), cmp);
    int mx = 0;
    for (int i = 1; i < pointsSize; i++) {
        mx = MAX(points[i][0] - points[i - 1][0], mx);
    }
    return mx;
}

[sol1-JavaScript]

var maxWidthOfVerticalArea = function(points) {
    points.sort((a, b) => a[0] - b[0]);
    let mx = 0;
    for (let i = 1; i < points.length; i++) {
        mx = Math.max(points[i][0] - points[i - 1][0], mx);
    }
    return mx;
};

[sol1-Golang]

func maxWidthOfVerticalArea(points [][]int) (ans int) {
    sort.Slice(points, func(i, j int) bool {
        return points[i][0] < points[j][0]
    })
    for i := 1; i < len(points); i++ {
        ans = max(ans, points[i][0]-points[i-1][0])
    }
    return
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

复杂度分析

• 时间复杂度：O(n \log n)，其中 n 是输入数组的长度，排序消耗 O(n \log n) 时间复杂度。

• 空间复杂度：O(\log n)，为排序的空间复杂度。