3102. 最小化曼哈顿距离

Hard

题目描述

给定一个表示二维平面上一些点的整数坐标的数组 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

解题思路

这道题需要理解曼哈顿距离的本质。对于两点 [xi, yi] 和 [xj, yj]，曼哈顿距离为 |xi - xj| + |yi - yj|。

关键观察： 曼哈顿距离可以通过坐标变换简化计算。将每个点 [x, y] 转换为 [x-y, x+y]，那么两点间的曼哈顿距离就等于转换后坐标在两个维度上的最大差值，即 max(|u1-u2|, |v1-v2|)，其中 u = x-y, v = x+y。

核心思想： 对于转换后的坐标系，所有点间的最大曼哈顿距离等于 max(max_u - min_u, max_v - min_v)，其中 max_u, min_u 是所有点u坐标的最大值和最小值，max_v, min_v 是所有点v坐标的最大值和最小值。

解法策略：

将所有点转换到新坐标系 [x-y, x+y]
找到决定最大距离的关键点（u或v坐标的最大值/最小值点）
只需要尝试移除这些关键点，因为只有移除它们才可能减小最大距离
对每个候选移除点，计算剩余点的最大曼哈顿距离
返回所有结果中的最小值

这种方法避免了暴力枚举所有点，大大提高了效率。

代码实现

class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        int n = points.size();
        vector<pair<int, int>> transformed(n);
        
        // 坐标变换：[x,y] -> [x-y, x+y]
        for (int i = 0; i < n; i++) {
            transformed[i] = {points[i][0] - points[i][1], points[i][0] + points[i][1]};
        }
        
        // 找到u和v坐标的最值及其索引
        int max_u = transformed[0].first, min_u = transformed[0].first;
        int max_v = transformed[0].second, min_v = transformed[0].second;
        int max_u_idx = 0, min_u_idx = 0, max_v_idx = 0, min_v_idx = 0;
        
        for (int i = 1; i < n; i++) {
            if (transformed[i].first > max_u) {
                max_u = transformed[i].first;
                max_u_idx = i;
            }
            if (transformed[i].first < min_u) {
                min_u = transformed[i].first;
                min_u_idx = i;
            }
            if (transformed[i].second > max_v) {
                max_v = transformed[i].second;
                max_v_idx = i;
            }
            if (transformed[i].second < min_v) {
                min_v = transformed[i].second;
                min_v_idx = i;
            }
        }
        
        // 候选移除点：决定最大距离的关键点
        set<int> candidates = {max_u_idx, min_u_idx, max_v_idx, min_v_idx};
        
        int result = INT_MAX;
        
        // 尝试移除每个候选点
        for (int remove_idx : candidates) {
            int new_max_u = INT_MIN, new_min_u = INT_MAX;
            int new_max_v = INT_MIN, new_min_v = INT_MAX;
            
            for (int i = 0; i < n; i++) {
                if (i == remove_idx) continue;
                new_max_u = max(new_max_u, transformed[i].first);
                new_min_u = min(new_min_u, transformed[i].first);
                new_max_v = max(new_max_v, transformed[i].second);
                new_min_v = min(new_min_v, transformed[i].second);
            }
            
            int max_dist = max(new_max_u - new_min_u, new_max_v - new_min_v);
            result = min(result, max_dist);
        }
        
        return result;
    }
};

class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        n = len(points)
        
        # 坐标变换：[x,y] -> [x-y, x+y]
        transformed = [(x - y, x + y) for x, y in points]
        
        # 找到u和v坐标的最值及其索引
        u_coords = [p[0] for p in transformed]
        v_coords = [p[1] for p in transformed]
        
        max_u_idx = u_coords.index(max(u_coords))
        min_u_idx = u_coords.index(min(u_coords))
        max_v_idx = v_coords.index(max(v_coords))
        min_v_idx = v_coords.index(min(v_coords))
        
        # 候选移除点：决定最大距离的关键点
        candidates = {max_u_idx, min_u_idx, max_v_idx, min_v_idx}
        
        result = float('inf')
        
        # 尝试移除每个候选点
        for remove_idx in candidates:
            remaining = [transformed[i] for i in range(n) if i != remove_idx]
            
            u_coords = [p[0] for p in remaining]
            v_coords = [p[1] for p in remaining]
            
            max_dist = max(max(u_coords) - min(u_coords), max(v_coords) - min(v_coords))
            result = min(result, max_dist)
        
        return result

public class Solution {
    public int MinimumDistance(int[][] points) {
        int n = points.Length;
        var transformed = new (int u, int v)[n];
        
        // 坐标变换：[x,y] -> [x-y, x+y]
        for (int i = 0; i < n; i++) {
            transformed[i] = (points[i][0] - points[i][1], points[i][0] + points[i][1]);
        }
        
        // 找到u和v坐标的最值及其索引
        int maxU = transformed[0].u, minU = transformed[0].u;
        int maxV = transformed[0].v, minV = transformed[0].v;
        int maxUIdx = 0, minUIdx = 0, maxVIdx = 0, minVIdx = 0;
        
        for (int i = 1; i < n; i++) {
            if (transformed[i].u > maxU) {
                maxU = transformed[i].u;
                maxUIdx = i;
            }
            if (transformed[i].u < minU) {
                minU = transformed[i].u;
                minUIdx = i;
            }
            if (transformed[i].v > maxV) {
                maxV = transformed[i].v;
                maxVIdx = i;
            }
            if (transformed[i].v < minV) {
                minV = transformed[i].v;
                minVIdx = i;
            }
        }
        
        // 候选移除点：决定最大距离的关键点
        var candidates = new HashSet<int> { maxUIdx, minUIdx, maxVIdx, minVIdx };
        
        int result = int.MaxValue;
        
        // 尝试移除每个候选点
        foreach (int removeIdx in candidates) {
            int newMaxU = int.MinValue, newMinU = int.MaxValue;
            int newMaxV = int.MinValue, newMinV = int.MaxValue;
            
            for (int i = 0; i < n; i++) {
                if (i == removeIdx) continue;
                newMaxU = Math.Max(newMaxU, transformed[i].u);
                newMinU = Math.Min(newMinU, transformed[i].u);
                newMaxV = Math.Max(newMaxV, transformed[i].v);
                newMinV = Math.Min(newMinV, transformed[i].v);
            }
            
            int maxDist = Math.Max(newMaxU - newMinU, newMaxV - newMinV);
            result = Math.Min(result, maxDist);
        }
        
        return result;
    }
}

/**
 * @param {number[][]} points
 * @return {number}
 */
var minimumDistance = function(points) {
    const n = points.length;
    
    // Transform points to u = x + y, v = x - y
    const transformed = points.map(([x, y]) => [x + y, x - y]);
    
    // Sort by u and v coordinates
    const sortedU = [...transformed].sort((a, b) => a[0] - b[0]);
    const sortedV = [...transformed].sort((a, b) => a[1] - b[1]);
    
    // Find extreme points
    const minU = sortedU[0];
    const maxU = sortedU[n - 1];
    const minV = sortedV[0];
    const maxV = sortedV[n - 1];
    
    // The maximum distance is determined by one of these pairs
    const candidates = new Set([minU, maxU, minV, maxV]);
    
    let minMaxDist = Infinity;
    
    // Try removing each candidate point
    for (const candidate of candidates) {
        const remaining = transformed.filter(p => p !== candidate);
        
        if (remaining.length < 2) continue;
        
        let maxDist = 0;
        for (let i = 0; i < remaining.length; i++) {
            for (let j = i + 1; j < remaining.length; j++) {
                const dist = Math.max(
                    Math.abs(remaining[i][0] - remaining[j][0]),
                    Math.abs(remaining[i][1] - remaining[j][1])
                );
                maxDist = Math.max(maxDist, dist);
            }
        }
        
        minMaxDist = Math.min(minMaxDist, maxDist);
    }
    
    // Also try removing points that might not be extreme but could reduce max distance
    const allPoints = new Set(transformed.map(p => p.join(',')));
    
    for (const point of transformed) {
        const remaining = transformed.filter(p => p !== point);
        
        const remU = remaining.map(p => p[0]).sort((a, b) => a - b);
        const remV = remaining.map(p => p[1]).sort((a, b) => a - b);
        
        const maxDist = Math.max(
            remU[remU.length - 1] - remU[0],
            remV[remV.length - 1] - remV[0]
        );
        
        minMaxDist = Math.min(minMaxDist, maxDist);
    }
    
    return minMaxDist;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度	时间复杂度	空间复杂度
时间	O(n)	O(n)
空间	O(n)	O(n)

说明：

时间复杂度：O(n)，需要遍历所有点进行坐标变换和找最值，候选点最多4个，每次计算剩余点的最值也是O(n)
空间复杂度：O(n)，存储转换后的坐标数组

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析