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

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

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

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

输入：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

Solutions

class Solution {
    public int maxWidthOfVerticalArea(int[][] points) {
        AtomicReference<Integer> last = new AtomicReference<>((int) 1e5), max = new AtomicReference<>(0);
        Arrays.stream(points).sorted(Comparator.comparing(x->x[0])).mapToInt(x->x[0]).forEachOrdered(x->{max.set(Math.max(max.get(), x - last.get()));last.set(x);});
        return max.get();
    }
}

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

Ideas

• 方法一：排序

  我们可以对数组 points按照 x 升序排列，获取相邻点之间 x* 的差值的最大值。

• 桶排序

  基于计数排序的思路，计算point[0]的最大最小值作为桶索引的边界，通过定义bucket_size，将整个数据范围均匀地划分为若干个桶，每个桶中的数据有序，避免对全量数据进行一次性排序。

  1. 计算point[0]的最大最小值。
  2. 设置桶的大小bucket_size。
  3. 根据数据范围和桶的大小计算出桶的个数，bucket_cnt = (maxValue - minValue) / bucket_size + 1，并初始化桶。
  4. 遍历points数组，根据x坐标计算其属于哪个桶，并将其加入桶中。
  5. 对于每个有数据的桶，进行排序（排序算法自定义）。
  6. 遍历有数据的桶中的有序数据，计算相邻元素的差，并保存最大值作为结果。

  class Solution {
    
      // 计算当前数组中的最大最小值
      private static int[] getMinAndMax(int[][] points) {
          int maxValue = points[0][0];
          int minValue = points[0][0];
          for (int[] point : points) {
              if (point[0] > maxValue) {
                  maxValue = point[0];
              } else if (point[0] < minValue) {
                  minValue = point[0];
              }
          }
          return new int[] { minValue, maxValue };
      }
    
      public int maxWidthOfVerticalArea(int[][] points) {
          int n = points.length;
          if (n == 2) return Math.abs(points[0][0] - points[1][0]);
          int[] extremum = getMinAndMax(points);
          int minValue = extremum[0];
          int maxValue = extremum[1];
          // 初始化桶的大小，直接影响内存和时间
          int bucket_size = 100000;
          // 根据设定的桶大小计算桶的数量
          int bucket_cnt = (maxValue - minValue) / bucket_size + 1;
          List<List<Integer>> buckets = new ArrayList<>();
          for (int i = 0; i < bucket_cnt; i++) {
              // 初始化每个桶
              buckets.add(new ArrayList<Integer>());
          }
          for (int[] point : points) {
              // 计算数据的索引位置并加入对应桶
              int idx = (point[0] - minValue) / bucket_size;
              buckets.get(idx).add(point[0]);
          }
          for (int i = 0; i < buckets.size(); i++) {
              // 如果该桶中有数据，将桶中数据排序
              if (buckets.get(i).size() > 1) {
                  Collections.sort(buckets.get(i));
                  buckets.set(i, buckets.get(i));
              }
          }
          int ans = 0, pre = -1;
          for (List<Integer> bucket : buckets) {
              // 如果桶中有数据，计算与前一个数据的差，取最大值作为结果
              if (bucket.size() > 0){
                  for (int point : bucket) {
                      if (pre >= 0){
                          ans = Math.max(ans, point - pre);
                      }
                      pre = point;
                  }
              }
          }
          return ans;
      }
  }