LeetCode-3102 最小化曼哈顿距离

LeetCode-3102 最小化曼哈顿距离 #

Solution 1 #

核心在于了解二维情况下曼哈顿距离与切比雪夫距离之间的转化. 对于点 $(x_1, y_1)$ 与点 $(x_2, y_2)$ , 作变换 $(x, y) = (\frac{a - b}{2}, \frac{a + b}{2})$ , 则这两个点的曼哈顿距离 $\vert x_1 - x_2\vert + \vert y_1 - y_2\vert = \max{({x_1 - x_2 + y_1 - y_2, x_1 - x_2 - y_1 + y_2, -x_1 + x_2 + y_1 - y_2, -x_1 + x_2 - y_1 + y_2})} = \max{({a_1 - a_2, - b_1 + b_2, b_1 - b_2, - a_1 + a_2})}=\max{({\vert a_1 - a_2\vert, \vert b_1 - b_2\vert})}$ . 因此, 一系列点 ${(x_i, y_i)}$ 的最大曼哈顿距离即为 $\max({\max({{a_i}}) - \min{({a_i})}}, {\max({{b_i}}) - \min{({b_i})}})$ . 遍历想要去掉的点更新答案即可. 代码如下:

from sortedcontainers import SortedList

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        a, b = SortedList(), SortedList()
        for x, y in points:
            a.add(x + y)
            b.add(y - x)
            
        ans = inf

        for x, y in points:
            a.remove(x + y)
            b.remove(y - x)
            ans = min(ans, max(a[-1] - a[0], b[-1] - b[0]))
            a.add(x + y)
            b.add(y - x)
        
        return ans