一、題目

1、題目描述

給你一個下標從?0?開始的數組?points?，它表示二維平面上一些點的整數坐標，其中?points[i] = [xi, yi]?。

兩點之間的距離定義為它們的

曼哈頓距離

。

請你恰好移除一個點，返回移除后任意兩點之間的?最大?距離可能的?最小?值。

2、接口描述

python3

??

class Solution:def minimumDistance(self, points: List[List[int]]) -> int:

cpp

??

class Solution {
public:int minimumDistance(vector<vector<int>>& points) {}
};

C#

??

public class Solution {public int MinimumDistance(int[][] points) {}
}

3、原題鏈接

3102. 最小化曼哈頓距離

---

二、解題報告

1、思路分析

有的做法是將曼哈頓距離轉化為切比雪夫距離的，個人還是比較喜歡下面這種做法，也是當初周賽的時候寫的做法：

對于任意兩個坐標(a, b), (c, d)

不妨設其曼哈頓距離為 a - c + b - c = a + b - c - d

我們發現坐標(a, b)和(c, d)曼哈頓距離中每個維度的系數相反

而對于二維坐標的系數無非就(-1, -1), (-1, 1), (1, -1), (1, 1)4種情況

每種情況下的最大值和最小值之差 的 最大值就是我們的最大曼哈頓距離

該做法可以推廣到n維坐標，時間復雜度為(2^N * M)M為坐標個數

2、復雜度

時間復雜度： O(4n)空間復雜度：O(n)

3、代碼詳解

python3

??

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
class Solution:def minimumDistance(self, points: List[List[int]]) -> int:n = len(points)res = 10**9buf = []tt = 0for a, b in (1, 1), (-1, -1), (1, -1), (-1, 1):ma, mi = -10**9, 10**9mai = mii = -1for i, (x, y) in enumerate(points):t = a * x + b * yif t > ma:ma, mai = t, iif t < mi:mi, mii = t, itt = fmax(tt, ma - mi)if ma - mi > tt:tt = ma - mibuf = [mai, mii]elif ma - mi == tt:buf.extend([mai, mii])for i in buf:tt = 0for a, b in (1, 1), (-1, -1), (1, -1), (-1, 1):ma, mi = -10**9, 10**9for j, (x, y) in enumerate(points):if j == i:continuet = a * x + b * yma = fmax(ma, t)mi = fmin(mi, t)tt = fmax(tt, ma - mi)res = fmin(res, tt)return res

cpp

??

class Solution {
public:int minimumDistance(vector<vector<int>>& points) {int n = points.size(), ret = 1e9, s = 0;vector<int> buf;for(int i = 0, ed = (1 << 2); i < ed; i++){int ma = -1e9, mi = 1e9, mai, mii;for(int j = 0, s; j < n; j++){int sum = 0;for(int k = 0; k < 2; k++)if(i >> k & 1) sum -= points[j][k];else sum += points[j][k];if(sum > ma) ma = sum, mai = j;if(sum < mi) mi = sum, mii = j;}if(ma - mi > s) s = ma - mi, buf = { mai, mii };else if(ma - mi == s) buf.insert(buf.end(), { mai, mii } );}for(auto x : buf){s = 0;for(int i = 0, ed = (1 << 2); i < ed; i++){int ma = -1e9, mi = 1e9, mai, mii;for(int j = 0, s; j < n; j++){if(j == x) continue;int sum = 0;for(int k = 0; k < 2; k++){if(i >> k & 1) sum -= points[j][k];else sum += points[j][k];}if(sum > ma) ma = sum, mai = j;if(sum < mi) mi = sum, mii = j;}if(ma - mi > s) s = ma - mi;}ret = min(ret , s);}return ret;}
};

C#

??

using System;
using System.Collections.Generic;
using System.Linq;public class Solution
{public int MinimumDistance(IList<IList<int>> points){int n = points.Count;int res = (int)Math.Pow(10, 9);List<int> buf = new List<int>();int tt = 0;Func<int, int, int> fmax = (x, y) => x > y ? x : y;Func<int, int, int> fmin = (x, y) => x < y ? x : y;var d = new List<(int, int)> { (1, 1), (-1, -1), (1, -1), (-1, 1) };foreach (var (a, b) in d){int ma = int.MinValue, mi = int.MaxValue;int mai = -1, mii = -1;for (int i = 0; i < points.Count; i++){int x = points[i][0];int y = points[i][1];int t = a * x + b * y;if (t > ma) {ma = t;mai = i;}if (t < mi) {mi = t;mii = i;}}tt = fmax(tt, ma - mi);if (ma - mi > tt){tt = ma - mi;buf = new List<int> { mai, mii };}else if (ma - mi == tt){buf.AddRange(new List<int> { mai, mii });}}foreach (int i in buf){tt = 0;foreach (var (a, b) in d){int ma = int.MinValue, mi = int.MaxValue;for (int j = 0; j < points.Count; j++){if (j == i) continue;int x = points[j][0];int y = points[j][1];int t = a * x + b * y;ma = fmax(ma, t);mi = fmin(mi, t);}tt = fmax(tt, ma - mi);}res = fmin(res, tt);}return res;}
}