3102.最小化曼哈顿距离

解题思路

分析时间复杂度，计算任意两点的曼哈顿距离达到$O(n^2)$，会超时需要优化。
因此优化可以将曼哈顿距离与切比雪夫距离的相互关系找出来，然后转换成求切比雪夫距离的方式，得到
$distance(A,B)=max(|(x_1-y_1)-(x_2-y_2)|,|(x_1+y_1)-(x_2+y_2)|)$
。这样，只需要计算每个点的坐标之差、坐标之和即可。
这样，曼达顿距离的最大值，即最大值与最小值的差的最大值。
删除某个点，删除对应的点然后重新计算即可。

曼哈顿距离与切比雪夫距离的相互转换

• 曼哈顿坐标系是通过切比雪夫坐标系旋45°后，再缩小到原来的一半得到的。
  将一个点 $(x,y)$ 的坐标变为 $(x+y,x-y)$ 后，原坐标系中的曼哈顿距离等于新坐标系中的切比雪夫距离。
  将一个点 $(x,y)$ 的坐标变为 $(\frac{x+y}{2},\frac{x-y}{2})$ 后，原坐标系中的切比雪夫距离等于新坐标系中的曼哈顿距离。
  碰到求切比雪夫距离或曼哈顿距离的题目时，我们往往可以相互转化来求解。两种距离在不同的题目中有不同的优缺点，应该灵活运用。

Java

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;
    }
}

C++

class Solution {
public:
    int minimumDistance(vector<vector<int>>& points) {
        // 维护两个集合
        multiset<int> sx, sy;
        for (auto & p : points){
            sx.emplace(p[0] - p[1]);
            sy.emplace(p[0] + p[1]);

        }
        int res = INT_MAX;
        for (auto & p :points){
            // 先消除
            sx.erase(sx.find(p[0] - p[1]));
            sy.erase(sy.find(p[0] + p[1]));
            // 更新
            res = min(res, max(*sx.rbegin() - *sx.begin(), *sy.rbegin() - *sy.begin()));
            sx.emplace(p[0] - p[1]);
            sy.emplace(p[0] + p[1]); // 恢复

        }
        return res;
    }
};

Python

from sortedcontainers import SortedList
class Solution:
    def minimumDistance(self, points: List[List[int]]) -> int:
        sx = SortedList(p[0] - p[1] for p in points)
        sy = SortedList(p[0] + p[1] for p in points)
        res = float('inf')
        for p in points:
            sx.remove(p[0] - p[1])
            sy.remove(p[0] + p[1])
            res = min(res, max(sx[-1] - sx[0], sy[-1] - sy[0]))
            sx.add(p[0] - p[1])
            sy.add(p[0] + p[1])
        return res