3102. 最小化曼哈顿距离——leetcode

给你一个下标从 0 开始的数组 points ，它表示二维平面上一些点的整数坐标，其中 points[i] = [xi, yi] 。

两点之间的距离定义为它们的曼哈顿距离。

请你恰好移除一个点，返回移除后任意两点之间的 最大 距离可能的 最小 值。

示例：

输入：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 。

官方题解： 

class Solution {
    public int minimumDistance(int[][] points) {
        TreeMap<Integer, Integer> sx = new TreeMap<Integer, Integer>();
        TreeMap<Integer, Integer> sy = new TreeMap<Integer, Integer>();
        for (int[] p : points) {
            sx.put(p[0] - p[1], sx.getOrDefault(p[0] - p[1], 0) + 1);
            sy.put(p[0] + p[1], sy.getOrDefault(p[0] + p[1], 0) + 1);
        }
        int res = Integer.MAX_VALUE;
        for (int[] p : points) {
            sx.put(p[0] - p[1], sx.get(p[0] - p[1]) - 1);
            if (sx.get(p[0] - p[1]) == 0) {
                sx.remove(p[0] - p[1]);
            }
            sy.put(p[0] + p[1], sy.get(p[0] + p[1]) - 1);
            if (sy.get(p[0] + p[1]) == 0) {
                sy.remove(p[0] + p[1]);
            }
            res = Math.min(res, Math.max(sx.lastKey() - sx.firstKey(), sy.lastKey() - sy.firstKey()));
            sx.put(p[0] - p[1], sx.getOrDefault(p[0] - p[1], 0) + 1);
            sy.put(p[0] + p[1], sy.getOrDefault(p[0] + p[1], 0) + 1);
        }
        return res;
    }
}

今天又破戒了，看了官方题解，这里对力扣官方提交进行详细解释（这里是up的个人理解，如果有错误请指出）：

对题意进行理解：

• 曼哈顿距离不是两点间距离；
• 任意去掉一个点，找到是此时任意两点间最大值的最小值；

解题思路：

        枚举出去掉一个点后任意两点的最大值的所有情况，最后取最小值。

如果只是简单的枚举，包超时的，这里就要在数学上进行转换：

曼哈顿距离

当时，

当时，

当时，

当时，

以代码形式合成一下：

length = Math.max(Math.abs(x1+y1-x2-y2),Math.abs(x1-y1+-x2+y2));

        这里，官方题解用两个TreeMap记录并排序了各个点x-y和x+y的情况，用value来判断该点是否被去掉，在第一个循环中，记录x-y和x+y的情况，而在第二个循环中，先将i处的点移除（通过key让value-1，判断其是否为0，为0则删除），然后寻找最大的x-y减去最小的x-y和最大的x+y减去最小的x+y，将其看作两个点，刚好是x1+y2-y1-x2和x1+y1-x2-y2，对其分别取绝对值，找出最大值，最后在与res对比，找出最小值，返回res。