LeetCode 1637. The widest vertical area between two points without any point

1637. The widest vertical area between two points without any points

Here you are. n Points on a two-dimensional plane points , among points[i] = [xi, yi] , Please return the point between two points without any point inside The widest vertical area Width .

Vertical area Is defined as a fixed width , and y An area on an axis that extends infinitely （ That is, the height is infinite ）. The widest vertical area The vertical area with the largest width .

Please note that , Vertical area On the edge The point of be not in In the area .

Example 1：

 Input ：points = [[8,7],[9,9],[7,4],[9,7]]
 Output ：1
 explain ： The red area and the blue area are both optimal areas .

Example 2：

 Input ：points = [[3,1],[9,0],[1,0],[1,4],[5,3],[8,8]]
 Output ：3

Tips ：

• n == points.length
• 2 <= n <= 105
• points[i].length == 2
• 0 <= xi, yi <= 109

Two 、 Method 1

Maximum sorting value , Just look at the abscissa comparison

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

Complexity analysis

• Time complexity ：O(nlogn).

• Spatial complexity ：O(1).