目标
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。
两点之间的距离定义为它们的 曼哈顿距离。两个单元格 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。
请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。
示例 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 <= 10^5
- points[i].length == 2
1 <= points[i][0], points[i][1] <= 10^8
提示：
- Notice that the Manhattan distance between two points [xi, yi] and [xj, yj] is max({xi - xj + yi - yj, xi - xj - yi + yj, - xi + xj + yi - yj, - xi + xj - yi + yj}).
- If you replace points as [xi - yi, xi + yi] then the Manhattan distance is max(max(xi) - min(xi), max(yi) - min(yi)) over all i.
- After those observations, the problem just becomes a simulation. Create multiset of points [xi - yi, xi + yi], you can iterate on a point you might remove and get the maximum Manhattan distance over all other points.
思路
有一些二维平面上的整数坐标点，移除其中一个点，求任意两点之间曼哈顿距离最大值的最小值。
n个点之间的曼哈顿距离有C(n,2) = n * (n - 1) / 2 个，移除其中一个点，最大值可能发生变化，需要找到其中最小的。
问题的关键是如何计算n个点之间曼哈顿距离的最大值，如果暴力计算，找出最大值的时间复杂度是 O(n^2)，还要依次移除一个点找到其中的最小值，综合起来时间复杂度是 O(n^3)。点的个数最多 10^5，暴力求解会超时。
我么需要考虑曼哈顿距离有什么特性，找出最大值需要每一个都遍历吗？移除一个点对最大值有什么影响，需要重新计算吗？
看了题目的提示是使用变量替换将问题转化：两点(xi, yi) 与 (xj, yj) 之间的曼哈顿距离为|xi - xj| + |yi - yj|，去掉绝对值即 max({xi - xj + yi - yj, xi - xj - yi + yj, - xi + xj + yi - yj, - xi + xj - yi + yj})，令 ui = xi - yi， vi = xi + yi，则点 (xi, yi) 与 (xj, yj) 之间的曼哈顿距离转换为 max({vi - vj, ui - uj, uj - ui, vj - vi}) = max({|vi - vj|, |ui- uj|})，对于所有的 i,j，曼哈顿距离的最大值为 max({max(vi) - min(vi), max(ui) - min(ui)})。这样找出曼哈顿距离最大值的时间复杂度减少为 O(n)。
于是，我们只需要将坐标点转化为 (ui, vi)，依次去除某个坐标点，再找出 u、v 的最大值与最小值即可。试了一下，O(n^2)的时间复杂度仍会超时。
我们可以记录一下vi、ui取最大最小值时的坐标，然后排除这几个坐标点后找出其中的最小值，最坏的情况即坐标没有重复，时间复杂度为O(4n)。
我也尝试了记录次大与次小值，试图将复杂度降为 O(n)，但需要考虑去除掉相应坐标点后，另一个坐标是否会受到影响。例如，max({max(vi) - min(vi), max(ui) - min(ui)}) 假如我们删去了vi最大的坐标，取次大的vi，但是后面ui的最大与最小是否受到影响？
因此我们不仅需要一次遍历获取到最大与次大，还要再次遍历比较当前值是否是最大或最小，如果是则取次大或次小。需要注意，这里的最大与次大以及最小与次小的值可以相同。更进一步，如果我们同时保存了x、y 取最大、最小的四个坐标，我们只需排除这4个坐标即可，其它坐标对最大距离没有影响。
看了官网题解，转换后的距离称为切比雪夫距离。事实上，max({|vi - vj|, |ui - uj|}) 计算的是 (vi, ui) (vj, uj) 两点曼哈顿距离投影到 x 轴(|vi - vj|) 和 y 轴(|ui - uj|)的线段长度的最大值，即切比雪夫距离。注意本题中的u、v对应题解中v、u，并且使用的是x-y，而非y-x，不过对于求解没有什么影响，无非是关于坐标轴镜像了一下。
代码
/**
* @date 2024-07-09 10:20
*/
public class MinimumDistance3102 {
public int minimumDistance(int[][] points) {
for (int[] point : points) {
int u = point[0] - point[1];
int v = point[0] + point[1];
point[0] = u;
point[1] = v;
}
int n = points.length;
int res = Integer.MAX_VALUE;
int maxX = Integer.MIN_VALUE;
int minX = Integer.MAX_VALUE;
int maxY = Integer.MIN_VALUE;
int minY = Integer.MAX_VALUE;
int maxXIndex = -1, minXIndex = -1, maxYIndex = -1, minYIndex = -1;
List<Integer> exclude = new ArrayList<>();
for (int j = 0; j < n; j++) {
if (points[j][0] > maxX) {
maxX = points[j][0];
maxXIndex = j;
}
if (points[j][0] < minX) {
minX = points[j][0];
minXIndex = j;
}
if (points[j][1] > maxY) {
maxY = points[j][1];
maxYIndex = j;
}
if (points[j][1] < minY) {
minY = points[j][1];
minYIndex = j;
}
}
exclude.add(maxXIndex);
exclude.add(minXIndex);
exclude.add(maxYIndex);
exclude.add(minYIndex);
for (Integer i : exclude) {
maxX = Integer.MIN_VALUE;
minX = Integer.MAX_VALUE;
maxY = Integer.MIN_VALUE;
minY = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) {
if (i != j) {
maxX = Math.max(maxX, points[j][0]);
minX = Math.min(minX, points[j][0]);
maxY = Math.max(maxY, points[j][1]);
minY = Math.min(minY, points[j][1]);
}
}
res = Math.min(res, Math.max(maxX - minX, maxY - minY));
}
return res;
}
}
性能
