JZX轻语：简
LeetCode 3102 - 最小化曼哈顿距离
发表于2024年07月09日
两个点p0(x1, y1)和p1(x2, y2)的曼哈顿距离为|x1 - x2| + |y1 - y2|。不妨将绝对值分情况讨论，即有四种情况：
x1 >= x2，y1 >= y2，有x1 - x2 + y1 - y2 = (x1 + y1) - (x2 + y2)；x1 >= x2，y1 < y2，有x1 - x2 + y2 - y1 = (x1 - y1) - (x2 - y2)；x1 < x2，y1 >= y2，有x2 - x1 + y1 - y2 = (y1 - x1) - (y2 - x2)；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