实现这道题核心思路在于坐标变换。通过将曼哈顿距离转化为切比雪夫距离可以把求“最大距离”的问题简化为求“最值差”的问题。主要步骤是首先将所有点 (x, y) 变换为 (xy, x-y)此时原点的曼哈顿距离等于变换后点的切比雪夫距离即 max(|Δx|, |Δy|)。这样全局最大曼哈顿距离就变为变换后坐标中 max( (xy的最大值 - 最小值), (x-y的最大值 - 最小值) )。因此我们可以枚举删除每一个点用有序集合如 TreeMap动态维护剩余点的变换坐标并快速计算出当前的最大距离记录其中的最小值即可。javaimport java.util.TreeMap;class Solution {public int minimumDistance(int[][] points) {// 使用 TreeMap 来维护所有点变换后的坐标值key为坐标值value为该值的出现次数TreeMapInteger, Integer sumMap new TreeMap(); // 维护 xyTreeMapInteger, Integer diffMap new TreeMap(); // 维护 x-y// 1. 初始化所有点将变换后的坐标加入集合for (int[] p : points) {int sum p[0] p[1];int diff p[0] - p[1];sumMap.put(sum, sumMap.getOrDefault(sum, 0) 1);diffMap.put(diff, diffMap.getOrDefault(diff, 0) 1);}int ans Integer.MAX_VALUE;// 2. 尝试移除每一个点for (int[] p : points) {int sum p[0] p[1];int diff p[0] - p[1];// --- 从集合中移除当前点 ---// 移除 xy 值int cntSum sumMap.get(sum);if (cntSum 1) sumMap.remove(sum);else sumMap.put(sum, cntSum - 1);// 移除 x-y 值int cntDiff diffMap.get(diff);if (cntDiff 1) diffMap.remove(diff);else diffMap.put(diff, cntDiff - 1);// --- 计算移除当前点后剩余点之间的最大曼哈顿距离 ---// 此时的最大距离 max( (xy最大差), (x-y最大差) )int currentMaxDist Math.max(sumMap.lastKey() - sumMap.firstKey(),diffMap.lastKey() - diffMap.firstKey());// 更新全局答案取最小值ans Math.min(ans, currentMaxDist);// --- 将当前点重新加回集合以便下一个循环使用 ---sumMap.put(sum, sumMap.getOrDefault(sum, 0) 1);diffMap.put(diff, diffMap.getOrDefault(diff, 0) 1);}return ans;}}
DeepSeek LeetCode 3102. 最小化曼哈顿距离 Java实现
发布时间：2026/6/10 9:37:10
实现这道题核心思路在于坐标变换。通过将曼哈顿距离转化为切比雪夫距离可以把求“最大距离”的问题简化为求“最值差”的问题。主要步骤是首先将所有点 (x, y) 变换为 (xy, x-y)此时原点的曼哈顿距离等于变换后点的切比雪夫距离即 max(|Δx|, |Δy|)。这样全局最大曼哈顿距离就变为变换后坐标中 max( (xy的最大值 - 最小值), (x-y的最大值 - 最小值) )。因此我们可以枚举删除每一个点用有序集合如 TreeMap动态维护剩余点的变换坐标并快速计算出当前的最大距离记录其中的最小值即可。javaimport java.util.TreeMap;class Solution {public int minimumDistance(int[][] points) {// 使用 TreeMap 来维护所有点变换后的坐标值key为坐标值value为该值的出现次数TreeMapInteger, Integer sumMap new TreeMap(); // 维护 xyTreeMapInteger, Integer diffMap new TreeMap(); // 维护 x-y// 1. 初始化所有点将变换后的坐标加入集合for (int[] p : points) {int sum p[0] p[1];int diff p[0] - p[1];sumMap.put(sum, sumMap.getOrDefault(sum, 0) 1);diffMap.put(diff, diffMap.getOrDefault(diff, 0) 1);}int ans Integer.MAX_VALUE;// 2. 尝试移除每一个点for (int[] p : points) {int sum p[0] p[1];int diff p[0] - p[1];// --- 从集合中移除当前点 ---// 移除 xy 值int cntSum sumMap.get(sum);if (cntSum 1) sumMap.remove(sum);else sumMap.put(sum, cntSum - 1);// 移除 x-y 值int cntDiff diffMap.get(diff);if (cntDiff 1) diffMap.remove(diff);else diffMap.put(diff, cntDiff - 1);// --- 计算移除当前点后剩余点之间的最大曼哈顿距离 ---// 此时的最大距离 max( (xy最大差), (x-y最大差) )int currentMaxDist Math.max(sumMap.lastKey() - sumMap.firstKey(),diffMap.lastKey() - diffMap.firstKey());// 更新全局答案取最小值ans Math.min(ans, currentMaxDist);// --- 将当前点重新加回集合以便下一个循环使用 ---sumMap.put(sum, sumMap.getOrDefault(sum, 0) 1);diffMap.put(diff, diffMap.getOrDefault(diff, 0) 1);}return ans;}}
)
