LeetCode 题解工作台
最小化曼哈顿距离
给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [x i , y i ] 。 两点之间的距离定义为它们的 曼哈顿距离 。 请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。 示例 1： 输入： points = …
5
题型
5
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
对于两个点 $(x_1, y_1)$ 和 $(x_2, y_2)$，它们的曼哈顿距离为 $|x_1 - x_2| + |y_1 - y_2|$。我们可以将其转化为 $\max(x_1 - x_2, x_2 - x_1) + \max(y_1 - y_2, y_2 - y_1)$，即： $$
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个下标从 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:
def minimumDistance(self, points: List[List[int]]) -> int:
sl1 = SortedList()
sl2 = SortedList()
for x, y in points:
sl1.add(x + y)
sl2.add(x - y)
ans = inf
for x, y in points:
sl1.remove(x + y)
sl2.remove(x - y)
ans = min(ans, max(sl1[-1] - sl1[0], sl2[-1] - sl2[0]))
sl1.add(x + y)
sl2.add(x - y)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on sorting or scanning the transformed arrays, typically O(n log n) or O(n) with careful selection. Space complexity is O(n) for storing transformed values and tracking extremes. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Focus on using array math and Manhattan distance properties instead of brute-force pairwise comparisons.
- question_mark
Consider how removing extreme points affects the maximum distance efficiently.
- question_mark
Look for candidates by computing xi + yi and xi - yi to reduce unnecessary calculations.
常见陷阱
外企场景- error
Attempting to check all possible removals without limiting to extreme candidates causes TLE.
- error
Ignoring both xi + yi and xi - yi transformations can miss the true maximum distance.
- error
Assuming Manhattan distance can be minimized by removing a random point rather than a critical extreme.
进阶变体
外企场景- arrow_right_alt
Minimizing Manhattan distance when removing multiple points instead of one.
- arrow_right_alt
Maximizing the minimum distance between points after removing a point.
- arrow_right_alt
Applying the same approach to 3D coordinates with Manhattan distance.