阿狗工具

前事不忘，后事之师。

LC每日一题，参考 1637. 两点之间不包含任何点的最宽垂直区域，难度分1487。

题目

给你n个二维平面上的点 points ，其中 points[i] = [xi, yi]，请你返回两点之间内部不包含任何点的 最宽垂直区域 的宽度。
垂直区域 的定义是固定宽度，而 y 轴上无限延伸的一块区域（也就是高度为无穷大）。 最宽垂直区域 为宽度最大的一个垂直区域。
请注意，垂直区域 边上 的点 不在 区域内。

解题思路

• 排序：考虑对x坐标进行排序后计算相邻最大差值即为最宽垂直区域，y值不影响。

排序 13ms

class Solution {
    public int maxWidthOfVerticalArea(int[][] points) {
        //考虑计算x的相邻相差最大宽度
        // //方法一：取出x排序 考虑优先队列 53ms
        // int w = 0;
        // PriorityQueue<Integer> pq = new PriorityQueue<>();
        // for(int i = 0; i < points.length; i++) {
        //     pq.add(points[i][0]);
        // }
        // //遍历pq计算最大宽度
        // int min = pq.poll();
        // while(!pq.isEmpty()) {
        //     int next = pq.poll();
        //     if(next - min > w) w = next - min;
        //     min = next;
        // }
        // return w;
        //方法二：对points排序 39s
        // 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;
        //方法三：取出x建立数组排序 13ms
        int w = 0;
        int[] x = new int[points.length];
        for(int i = 0; i < points.length; i++) {
            x[i] = points[i][0];
        }
        Arrays.sort(x);
        for(int i = 1; i < x.length; i++) {
            w = Math.max(w,x[i] - x[i - 1]);
        }
        return w;
    }
}

复杂度分析

• 时间复杂度：O(nlogn)，排序时间O(nlogn)，遍历时间 O(n)。
• 空间复杂度：O(n)，x数组空间O(n)。

2023-03-30