本文只讨论二维空间中的曼哈顿距离与切比雪夫距离优化
设平面空间内存在两点,它们的坐标为$(x1,y1)$,$(x2,y2)$spa
则$dis=|x1-x2|+|y1-y2|$3d
即两点横纵坐标差之和blog
如图所示,图中$A,B$两点的曼哈顿距离为$AC+BC=4+3=7$排序
设平面空间内存在两点,它们的坐标为$(x1,y1)$,$(x2,y2)$内存
则$dis=max(|x1-x2|,|y1-y2|)$get
即两点横纵坐标差的最大值
im
$dis=max(AC,BC)=AC=4$img
二者的定义看上去好像毛线关系都没有,但实际上,这两种距离能够相互转化!di
咱们考虑最简单的状况,在一个二维坐标系中,设原点为$(0,0)$
若是用曼哈顿距离表示,则与原点距离为$1$的点会构成一个边长为$\sqrt{2}$的正方形
若是用切比雪夫距离表示,则与原点距离为$1$的点会构成一个边长为$2$的正方形
仔细对比这两个图形,咱们会发现这两个图形长得差很少,他们应该能够经过某种变换互相转化。
事实上,
将一个点$(x,y)$的坐标变为$(x+y,x-y)$后,原坐标系中的曼哈顿距离 $=$ 新坐标系中的切比雪夫距离
将一个点$(x,y)$的坐标变为$(\frac{x+y}{2},\frac{x-y}{2})$ 后,原坐标系中的切比雪夫距离 $=$ 新坐标系中的曼哈顿距离
切比雪夫距离在计算的时候须要取$max$,每每不是很好优化,对于一个点,计算其余点到该的距离的复杂度为$O(n)$
而曼哈顿距离只有求和以及取绝对值两种运算,咱们把坐标排序后能够去掉绝对值的影响,进而用前缀和优化,能够把复杂度降为$O(1)$