发表于 2024.07.09

• 两个点p0(x1, y1)和p1(x2, y2)的曼哈顿距离为|x1 - x2| + |y1 - y2|。不妨将绝对值分情况讨论，即有四种情况：

  1. x1 >= x2，y1 >= y2，有x1 - x2 + y1 - y2 = (x1 + y1) - (x2 + y2)；

  2. x1 >= x2，y1 < y2，有x1 - x2 + y2 - y1 = (x1 - y1) - (x2 - y2)；

  3. x1 < x2，y1 >= y2，有x2 - x1 + y1 - y2 = (y1 - x1) - (y2 - x2)；

  4. x1 < x2，y1 < y2，有x2 - x1 + y2 - y1 = (x2 + y2) - (x1 + y1)。

  不难得知，最大曼哈顿距离的点对，要么是x + y中最大和最小的两个点，要么是x - y中最大和最小的两个点(直观地讲，可以看成是两个对角线)。因此，要想移除某个点后任意两点间最大曼哈顿距离最小，要移除的点必然出自上述两个点对(4个点)中的某个点(不难证明，如果移除上述点对外的点，最大曼哈顿距离没有变化)。因此，我们可以先将所有点按照x + y和x - y的值排序以取得上述的点对，然后枚举这四个点，计算移除该点后的最大曼哈顿距离，取最小值即可。

  class Solution:
      def minimumDistance(self, points: List[List[int]]) -> int:
          def dist(p1: List[int], p2: List[int]) -> int:
              return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
  
          points1 = sorted(points, key=lambda item: item[0] + item[1])  # 按照 x + y 排序, 取最大和最小的两个点
          points2 = sorted(points, key=lambda item: item[1] - item[0])  # 按照 x - y 排序，取最大和最小的两个点
          cand_points = (points1[0], points1[-1], points2[0], points2[-1])  # 待移除的点必定在这四个点中
          ans = -1
          for cand in cand_points:
              # 枚举每个点，计算移除该点后的最大曼哈顿距离
              # 如果两个点对中的一个点是待移除的点，则取第二大/第二小的点
              diag_p1 = points1[-1] if points1[-1] != cand else points1[-2]
              diag_p2 = points1[0] if points1[0] != cand else points1[1]
              rev_diag_p1 = points2[-1] if points2[-1] != cand else points2[-2]
              rev_diag_p2 = points2[0] if points2[0] != cand else points2[1]
              max_dist = max(dist(diag_p1, diag_p2), dist(rev_diag_p1, rev_diag_p2))
              if ans == -1 or max_dist < ans:
                  ans = max_dist
          return ans

• LC 题目链接