周赛240331

第四题 100240

最小化曼哈顿距离

  • 题目大意：给定一个二维平面上的点集，求移除其中一个点后，剩余点集中任意两点之间的最大曼哈顿距离的最小值。

  • 实现思路：首先，对于曼哈顿距离而言，它的定义是两点在各个坐标轴上的差的绝对值之和。所以移除一个点后，影响到最大曼哈顿距离的主要是距离移除点最近的点。我们可以将点的坐标进行转换，将其转换为(x+y)和(x-y)的形式，这样在平面上的曼哈顿距离就可以等效为在转换后的坐标系下的欧几里得距离。然后我们用两个有序集合分别维护x+y和x-y的坐标轴上的值，分别为xset和yset。然后遍历每个点，从点集中移除一个点，更新最大距离，找到最小值。

from sortedcontainers import SortedList
class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        xset, yset = SortedList(), SortedList()
        for x, y in points:
            xset.add(x+y)
            yset.add(x-y)
        ans = inf
        for x, y in points:
            xx = x+y
            yy = x-y 
            xset.remove(xx)
            yset.remove(yy)
            ans = min( ans, max(xset[-1]-xset[0], yset[-1]-yset[0]) )
            xset.add(xx)
            yset.add(yy)
        return ans