题目描述
给你一个下标从 0 开始的数组 points
,它表示二维平面上一些点的整数坐标,其中 points[i] = [x_i, y_i]
。
两点之间的距离定义为它们的曼哈顿距离。
请你恰好移除一个点,返回移除后任意两点之间的 最大 距离可能的 最小 值。
样例
输入: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。
输入: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
算法1
(数学,有序集,枚举) $O(n \log n)$
- 先求一个集合中,两个点曼哈顿距离的最大值。
- 对于两个点 $(x1, y1)$ 和 $(x2, y2)$ 的曼哈顿距离,可以改写为 $\max(|(x1 + y1) - (x2 + y2)|, |(x1 - y1) - (x2 - y2)|)$。根据这个公式,可以求出点集中所有点横纵坐标之和与横纵坐标之差,然后找到横纵坐标之和最大的差值与横纵坐标之差最大的差值的最大值,就是点集中两个点曼哈顿距离的最大值。
- 如果恰好删除一个点,则可以使用有序集维护所有点的横纵坐标之和与横纵坐标之差,然后枚举被删掉的点,更新答案。
时间复杂度
- 预处理的时间复杂度为 $O(n \log n)$。
- 每次枚举删点的时间复杂度为 $O(\log n)$。
- 故总时间复杂度为 $O(n \log n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储有序集。
C++ 代码
class Solution {
public:
int minimumDistance(vector<vector<int>>& points) {
const int n = points.size();
multiset<int> s1, s2;
for (const auto &p : points) {
s1.insert(p[0] + p[1]);
s2.insert(p[0] - p[1]);
}
int ans = INT_MAX;
for (const auto &p : points) {
s1.erase(s1.find(p[0] + p[1]));
s2.erase(s2.find(p[0] - p[1]));
ans = min(ans,
max(*s1.rbegin() - *s1.begin(),
*s2.rbegin() - *s2.begin())
);
s1.insert(p[0] + p[1]);
s2.insert(p[0] - p[1]);
}
return ans;
}
};
算法2
(数学,枚举) $O(n)$
- 类似于算法 1,注意到,最终答案只与横纵坐标之和与横纵坐标之差的最大、次大,最小、次小值有关。
- 所以维护 8 个变量,分别表示横纵坐标之和的最大最小值与次大次小值,横纵坐标之差的最大最小值与次大次小值。
- 枚举删除的点时,根据当前点的横纵坐标之和与横纵坐标之差,决定是否是用最值还是次值来更新答案。
时间复杂度
- 预处理的时间复杂度为 $O(n)$。
- 每次枚举删点的时间复杂度为 $O(1)$。
- 故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int minimumDistance(vector<vector<int>>& points) {
const int n = points.size();
vector<int> p(4), d(4);
p[0] = p[1] = d[0] = d[1] = INT_MAX;
p[2] = p[3] = d[2] = d[3] = INT_MIN;
for (const auto &t : points) {
int x = t[0] + t[1], y = t[0] - t[1];
if (p[0] > x) {
p[1] = p[0]; p[0] = x;
} else if (p[1] > x) {
p[1] = x;
}
if (p[2] < x) {
p[3] = p[2]; p[2] = x;
} else if (p[3] < x) {
p[3] = x;
}
if (d[0] > y) {
d[1] = d[0]; d[0] = y;
} else if (d[1] > y) {
d[1] = y;
}
if (d[2] < y) {
d[3] = d[2]; d[2] = y;
} else if (d[3] < y) {
d[3] = y;
}
}
int ans = INT_MAX;
for (const auto &t : points) {
int x = t[0] + t[1], y = t[0] - t[1];
int pmi = p[0] < x ? p[0] : p[1];
int pma = p[2] > x ? p[2] : p[3];
int dmi = d[0] < y ? d[0] : d[1];
int dma = d[2] > y ? d[2] : d[3];
ans = min(ans, max(pma - pmi, dma - dmi));
}
return ans;
}
};