题目
给你一个下标从 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 <= 10^5$
- $ points[i].length == 2$
- $ 1 <= points[i][0], points[i][1] <= 10^8$
分析
暴力可以做：
- 枚举全部两点，计算距离，维护一个有序数组
- 计算删除每一个点，最大值中的最小值
需要进一步设计算法，简化距离计算！距离等价转换成比雪夫距离
距离等价转换成比雪夫距离——使用有序集合
class Solution {
public int minimumDistance(int[][] points) {
TreeMap<Integer, Integer> xs = new TreeMap<>();
TreeMap<Integer, Integer> ys = new TreeMap<>();
for (int[] p : points) {
xs.merge(p[0] + p[1], 1, Integer::sum);
ys.merge(p[1] - p[0], 1, Integer::sum);
}
int ans = Integer.MAX_VALUE;
for (int[] p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
if (xs.get(x) == 1) xs.remove(x);
else xs.merge(x, -1, Integer::sum); // 移除一个 x
if (ys.get(y) == 1) ys.remove(y);
else ys.merge(y, -1, Integer::sum); // 移除一个 y
int dx = xs.lastKey() - xs.firstKey();
int dy = ys.lastKey() - ys.firstKey();
ans = Math.min(ans, Math.max(dx, dy));
xs.merge(x, 1, Integer::sum);
ys.merge(y, 1, Integer::sum);
}
return ans;
}
}
维护最大次大、最小次小
class Solution {
public int minimumDistance(int[][] points) {
final int INF = Integer.MAX_VALUE;
int maxX1 = -INF,maxX2 = -INF,maxY1 = -INF,maxY2 = -INF;
int minX1 = INF,minX2 = INF,minY1 = INF,minY2 = INF;
for (int[] p : points) {
int x = p[0]+p[1];
int y = p[1]-p[0];
// x 最大次大
if(x > maxX1) {
maxX2 = maxX1;
maxX1 = x;
} else if (x > maxX2){
maxX2 = x;
}
// x 最小次小
if(x < minX1) {
minX2 = minX1;
minX1 = x;
} else if (x < minX2){
minX2 = x;
}
// y 最大次大
if(y > maxY1) {
maxY2 = maxY1;
maxY1 = y;
} else if (y > maxY2){
maxY2 = y;
}
// x 最小次小
if(y < minY1) {
minY2 = minY1;
minY1 = y;
} else if (y < minY2){
minY2 = y;
}
}
int ans = INF;
for (int[] p: points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
int dx = (x == maxX1 ? maxX2 : maxX1) - (x == minX1 ? minX2 : minX1);
int dy = (y == maxY1 ? maxY2 : maxY1) - (y == minY1 ? minY2 : minY1);
ans = Math.min(ans, Math.max(dx,dy));
}
return ans;
}
}
// 代码优化
class Solution {
public int minimumDistance(int[][] points) {
final int INF = Integer.MAX_VALUE;
int[] maxX = new int[2];
maxX[0] = -INF;
maxX[1] = -INF;
int[] minX = new int[2];
minX[0] = INF;
minX[1] = INF;
int[] maxY = new int[2];
maxY[0] = -INF;
maxY[1] = -INF;
int[] minY = new int[2];
minY[0] = INF;
minY[1] = INF;
for (int[] p : points) {
int x = p[0] + p[1];
int y = p[1] - p[0];
updateMax(maxX, x);
updateMin(minX, x);
updateMax(maxY, y);
updateMin(minY, y);
}
int ans = INF;
for (int[] p : points) {
ans = Math.min(ans, Math.max(getDa(maxX, minX, p[0] + p[1]), getDa(maxY, minY, p[1] - p[0])));
}
return ans;
}
private void updateMax(int[] maxA, int x) {
if (x > maxA[0]) {
maxA[1] = maxA[0];
maxA[0] = x;
} else if (x > maxA[1]) {
maxA[1] = x;
}
}
private void updateMin(int[] minA, int x) {
if (x < minA[0]) {
minA[1] = minA[0];
minA[0] = x;
} else if (x < minA[1]) {
minA[1] = x;
}
}
private int getDa(int[] maxA, int[] minA, int x) {
return (x == maxA[0] ? maxA[1] : maxA[0]) - (x == minA[0] ? minA[1] : minA[0]);
}
}
维护最大最小值下标
class Solution {
public int minimumDistance(int[][] points) {
final int INF = Integer.MAX_VALUE;
int maxX1 = -INF, maxX2 = -INF, maxY1 = -INF, maxY2 = -INF;
int minX1 = INF, minX2 = INF, minY1 = INF, minY2 = INF;
int maxXi = 0, minXi = 0, maxYi = 0, minYi = 0;
for (int i = 0; i < points.length; i++) {
int[] p = points[i];
int x = p[0] + p[1];
int y = p[1] - p[0];
// x 最大次大
if (x > maxX1) {
maxX2 = maxX1;
maxX1 = x;
maxXi = i;
} else if (x > maxX2) {
maxX2 = x;
}
// x 最小次小
if (x < minX1) {
minX2 = minX1;
minX1 = x;
minXi = i;
} else if (x < minX2) {
minX2 = x;
}
// y 最大次大
if (y > maxY1) {
maxY2 = maxY1;
maxY1 = y;
maxYi = i;
} else if (y > maxY2) {
maxY2 = y;
}
// y 最小次小
if (y < minY1) {
minY2 = minY1;
minY1 = y;
minYi = i;
} else if (y < minY2) {
minY2 = y;
}
}
int ans = INF;
for (int i : new int[]{maxXi, minXi, maxYi, minYi}) {
int dx = (i == maxXi ? maxX2 : maxX1) - (i == minXi ? minX2 : minX1);
int dy = (i == maxYi ? maxY2 : maxY1) - (i == minYi ? minY2 : minY1);
ans = Math.min(ans, Math.max(dx, dy));
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
