LC 100240. 最小化曼哈顿距离

https://leetcode.cn/problems/minimize-manhattan-distances/description/

看了评论才大概知道曼哈顿距离的某些特性 距离 - OI Wiki

$$

(1)|xi−xj|+|yi−yj|(2)=max(xi−xj,xj−xi)+max(yi−yj,yj−yi)(3)=max(xi−xj+yi−yj,xi−xj+yj−yi,xj−xi+yi−yj,xj−xi+yj−yi)(4)=max((xi+yi)−(xj+yj),(xi−yi)−(xj−yj),(xj−yj)−(xi−yi),(yj+xj)−(xi+xi)))(5)=max(abs((xi+yi)−(xj+yj)),abs((xi−yi)−(xj−yj)))

$$

所以最终我们关心的是(x+y), 以及(x-y)之间的最大差值，这个就是集合中中两点之间最大的曼哈顿距离。 

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        from sortedcontainers import SortedList
        s1, s2 = SortedList(), SortedList()
        for (x, y) in points:
            s1.add(x + y)
            s2.add(x - y)

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