题目：
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。两点之间的距离定义为它们的曼哈顿距离。
请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 1：
输入：points = [[3,10],[5,15],[10,2],[4,4]]
输出：12
解释：移除每个点后的最大距离如下所示：
- 移除第 0 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间，为 |5 - 10| + |15 - 2| = 18 。
- 移除第 1 个点后，最大距离在点 (3, 10) 和 (10, 2) 之间，为 |3 - 10| + |10 - 2| = 15 。
- 移除第 2 个点后，最大距离在点 (5, 15) 和 (4, 4) 之间，为 |5 - 4| + |15 - 4| = 12 。
- 移除第 3 个点后，最大距离在点 (5, 15) 和 (10, 2) 之间的，为 |5 - 10| + |15 - 2| = 18 。
在恰好移除一个点后，任意两点之间的最大距离可能的最小值是 12 。
示例 2：
输入：points = [[1,1],[1,1],[1,1]]
输出：0
解释：移除任一点后，任意两点之间的最大距离都是 0 。
提示：
3 <= points.length <= 105points[i].length == 21 <= points[i][0], points[i][1] <= 108
我是暴力之王
思路：
对于题目， 要判断的其实只是 曼哈顿距离
对于暴力解法，我们只需要计算每个曼哈顿距离就行
代码：
class Solution {
public:
int minimumDistance(vector<vector<int>>& points) {
// 暴力解法： O(n^3) 取每个元素当移除元素，然后统计剩余元素的最大距离
int n = points.size();
int min_dis = INT_MAX;
for (int i = 0; i < n; i++) {
// i 是要 删除的元素 索引
int max_dis = -1;
for (int j = 0; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (j != i && k != i) {
int dis = abs(points[j][0] - points[k][0]) + abs(points[j][1] - points[k][1]);
max_dis = max(max_dis, dis);
}
}
}
min_dis = min(min_dis, max_dis);
}
return min_dis;
}
};
数学转换法
思路：
暴力解法核心的复杂度就在于：
枚举删除点时， 计算剩余点之间的 曼哈顿距离
我们虚化剩余点这个概念， 不要以枚举的方式考虑points中的元素
题目要求移除一个点后，使得任意两点的曼哈顿的最大距离尽可能的小。根据题意分析，我们可以找到任意两点的曼哈顿距离的最大值，并记录构成最大值的点的集合 S，需要去掉的点一定存在于该集合 S 中，依次尝试去掉集合 S 中的某点，并计算剩余点构成的曼哈顿距离。由于需要计算任意两点的曼哈顿距离所需要的时间复杂度至少为 O(n^2)，因此该算法在题目给定的数量级下会超时，需要进行优化。
首先我们思考如何计算任意两点的最大距离，这里需要用到一些数学知识，可以参考「曼哈顿距离与切比雪夫距离的相互转化」。设两点 A,B 分别为 (x1, y1), (x2, y2)，此时 A,B 两点的曼哈顿距离为：
d(A, B) = |x1 - x2| + |y1 - y2|
= max(|(x1 - y1) - (x2 - y2)|, |(x1 + y1) - (x2 + y2)|)
对于每个点 (x,y)，我们分别计算它的坐标之和与坐标之差 x − y, x + y，并用有序集合 Sx, Sy 维护这些值，此时任意两点曼哈顿距离的最大值即为两个集合 Sx, Sy 中的最大值与该集合本身的最小值之差中取最大值。每次枚举点 (x′ ,y′)，从集合 Sx ,Sy 中删除对应的 (x′ − y′, x′ + y′)，然后再次计算最大的曼哈顿距离，计算完成后再恢复，枚举完成后即可得到最小的曼哈顿距离。
代码：
class Solution {
public:
int minimumDistance(vector<vector<int>>& points) {
// 这种思想 最妙的地方 就是将关注点弱化掉了， 不再将points中每个元素拿出来考虑
// 如果聚焦 points 的每个元素， 那么处理距离时 复杂度必然是巨大的
multiset<int> sx, sy;
for (auto& p : points) {
sx.emplace(p[0] - p[1]);
sy.emplace(p[0] + p[1]);
}
int res = INT_MAX;
for (auto& p : points) {
// p 就是本轮要 删除的
sx.erase(sx.find(p[0] - p[1]));
sy.erase(sy.find(p[0] + p[1]));
res = min(res, max(*sx.rbegin() - *sx.begin(), *sy.rbegin() - *sy.begin()));
sx.emplace(p[0] - p[1]);
sy.emplace(p[0] + p[1]);
}
return res;
}
};