LeetCode 3102. Minimize Manhattan Distances

April 1, 2024

周賽 391。看關鍵字猜題翻車了，我看到最大值最小化就想著二分答案，結果根本不是。

題目

輸入陣列 poins，代表二維平面上的某些整數坐標，其中 points[i] = [x_i, y_i]。

定義兩點之間的距離為他們的曼哈頓距離。

求正好移除一個點之後，剩餘點中的任意兩點之間的最大距離的最小值。

解法

先來看看曼哈頓距離的公式：

|x1 - x2| + |y2 - y2|

好像沒辦法直接拿來用。這種給定公式的題目，很多都要靠移項或是重排變數，進而消除變數之間的關聯。
總之先把礙事的絕對值處理掉。

對於 x 軸距離差來說，根據 x1 和 x2 的大小不同，有可能是 (x1 - x2) 或是 (x2 - x1)；對於 y 軸同理。
將絕對值拆掉後，相當於以下四個公式取最大值：

(x1 - x2) + (y1 - y2)
(x2 - x1) + (y1 - y2)
(x1 - x2) + (y2 - y1)
(x2 - x1) + (y2 - y1)

為了降低兩個點的關聯性，把來自同個坐標的變數放到一起：

x1 - x2 + y1 - y2 變成 x1 + y1 - x2 - y2
x2 - x1 + y1 - y2 變成 -x1 + y1 + x2 - y2
x1 - x2 + y2 - y1 變成 x1 - y1 - x2 + y2
x2 - x1 + y2 - y1 變成 -x1 - y1 + x2 + y2

並且基於對稱性，(p1, p2) 等價於 (p2, p1)，所以第一和第四項等價、第二和第三項等價。
再把係數提出來：

(x1 + y1) - (x2 + y2)
-(x1 - y1) + (x2 - y2)

最後，座標 (x, y) 被分解成 (x + y) 和 (x - y)，只要透過他們就能求出兩點距離。

剛才推出的是兩點之間的距離，那要怎麼找到任意兩點的最大值？
其實很簡單，為了使結果最大化，當然是代入他們的最大/最小值。

先求出所有點的 (x + y) 及 (x - y) 值，以有序容器保存，方便查詢極值。分別記做 A 和 B。
枚舉需要被移除的坐標 points[i] = (x, y)，先從 A 和 B 中暫時移除對應的值，依照上述公式求出最大距離，並更新答案最小值，然後再把剛才移除的值加回去。

時間複雜度 O(N log N)。
空間複雜度 O(N)。

from sortedcontainers import SortedList as SL

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        A = SL() # x + y
        B = SL() # x - y
        
        def add(x, y):
            A.add(x + y)
            B.add(x - y)
        
        def remove(x, y):
            A.remove(x + y)
            B.remove(x - y)
        
        for x, y in points:
            add(x, y)
            
        ans = inf
        for x, y in points:
            remove(x, y)
            dis = max(
                A[-1] - A[0],  # max(x1 + y1) - min(x2 + y2) 
                -B[0] + B[-1]  # -min(x1 - y1) + max(x2 - y2)  
            )
            ans = min(ans, dis)
            add(x, y)
            
        return ans

也可以不用有序容器，直接將 A, B 值帶上坐標索引排序。
枚舉刪除坐標索引 i 時額外檢查，若刪除的剛好是極值，則取次大/次小。

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        N = len(points)
        A = sorted([x + y, i] for i, (x, y) in enumerate(points))
        B = sorted([x - y, i] for i, (x, y) in enumerate(points))        
        
        ans = inf
        for i in range(N):
            minA = A[0][0] if i != A[0][1] else A[1][0]
            maxA = A[-1][0] if i != A[-1][1] else A[-2][0]            
            minB = B[0][0] if i != B[0][1] else B[1][0]
            maxB = B[-1][0] if i != B[-1][1] else B[-2][0]            
            dist = max(
                maxA - minA, # max(x1 + y1) - min(x2 + y2) 
                -minB + maxB # -min(x1 - y1) + max(x2 - y2)  
            )
            ans = min(ans, dist)
            
        return ans

mocowcow

題目

解法