曼哈顿距离最大值最小化：旋转45度转为切比雪夫距离求解

每日一题系列更新到第17期。这一期的标题看着像是几何题实际上考的是坐标系移动和切比雪夫距离Chebyshev distance的配合。题目背景很接地气平面上有n个点要选一个中心位置让所有点到这个中心位置的曼哈顿距离最大值尽量小。第一眼看到这个问题我脑子里跳出来的是“分别对x、y取中位数”结果样例直接挂了。后来把坐标系整体旋转45度用(xy, x-y)这组新坐标重新看问题曼哈顿距离会变成新坐标系下的切比雪夫距离最大值最小问题瞬间变成“用一个边与坐标轴平行的正方形盖住所有点”。这篇文章会把推导过程、证明、完整代码和调试经验一次讲透适合被坐标变换题坑过的同学也适合准备面试或算法竞赛但还没系统整理L1、L∞互换技巧的人。1. 把题目翻译成人话仓库选址和方形世界1.1 题目输入输出长什么样题面可以这样描述给定n个平面点坐标都是整数例如(0,0), (1,1), (2,0)。现在要找一个中心点(cx, cy)使得所有点到它的曼哈顿距离|x-cx| |y-cy|的最大值最小。输出这个最小的最大距离以及任意一个能达到最优值的中心点坐标。这个模型在现实里非常常见。比如要在城区里建一个应急物资仓库配送员只能沿着横竖街道走也就是只能走曼哈顿路线那么“最远的配送员跑多远”就是上面那个最大值。我们希望这个最远距离尽可能小也就是要优化最坏情况。另一个例子是外卖平台的取餐点选址骑手从不同方向过来路程按街区计算同样适用。这类问题很容易让人误以为“把x排序取中位数、y排序取中位数”就行因为求曼哈顿距离之和最小确实可以这样干。但题目要的是最大值最小不是总和最小。目标函数从求和变成取max之后中位数的位置就不对了。拿例子来说点(0,0), (1,1), (2,0)x的中位数是1y的中位数是1中心(1,1)到三个点的曼哈顿距离分别是2、0、2最大值是2。但如果你选中心(1,0)距离分别是1、1、1最大值是1明显更优。这说明问题没那么简单需要用几何结构重新理解。1.2 第一个朴素方案为什么会挂在继续推导之前我想先把这个误区讲透因为这是很多人第一次写代码时踩的坑。求曼哈顿距离总和最小本质上每个点是独立的中位数能均衡两侧的数量但求最大值最小比较的是“最远的那个点”中位数无法控制最远点的距离。一维的例子最直观数轴上三个点1、2、100。中位数是2最远距离是max(2-1, 100-2)98你去取均值51.5最远距离是max(51.5-1, 100-51.5)50.5。虽然均值不是整数但在这个问题里它比中位数好得多。二维情况下两个维度的“最优中心”可以分别取中点区间而不是取中位数。这个例子也说明了一个关键点最大值最小问题通常和“区间跨度”有关一个维度的最优取值往往落在最小值和最大值的中点附近。换个角度看要覆盖住一维数轴上所有点半径最小只能是跨度的一半中心点取中点。二维曼哈顿场景虽然不能直接拆成两个独立的一维问题但只要换一个坐标系它就能拆开这就是切比雪夫距离登场的地方。1.3 先建立直觉曼哈顿距离对应的方形世界曼哈顿距离的“单位圆”是一个旋转45度的正方形顶点在坐标轴上。切比雪夫距离的“单位圆”则是边与坐标轴平行的正方形。两者之间就差了一个旋转或者严格说差一个45度的旋转加缩放。切比雪夫距离有一个特别生活化的名字叫“棋盘距离”。想象国际象棋里的国王它一步可以朝八个方向走一格。从(x1,y1)走到(x2,y2)国王需要的最少步数就是max(|dx|, |dy|)。原因是国王每步横、竖、斜都能走水平差和竖直差中较大的那个决定步数。这个度量的几何意义非常清楚离原点切比雪夫距离不超过R的点正好围成一个边长为2R、边与坐标轴平行的正方形。所以“切比雪夫距离最小覆盖问题”本质上就是“找一个轴对齐的正方形盖住所有点”。这些直觉建立起来之后再回头看仓库选址问题曼哈顿距离的最坏情况优化能不能也变成一个“用方形去覆盖点”的问题答案是能做法就是把坐标系移动一下换成一组斜45度的坐标轴。下一节把公式推导完整写出来。2. 切比雪夫距离的几何直觉与公式基础2.1 切比雪夫距离的数学定义切比雪夫距离的定义式是d∞(A,B) max(|xA-xB|, |yA-yB|)。它和欧氏距离、曼哈顿距离并列是Lp距离族里p趋于无穷大的情况。之所以单独写一题来讲是因为它有一个很特别的几何性质它的等距线是正方形而且正方形的边和坐标轴平行。在很多算法题里切比雪夫距离经常以“国王走棋盘”“最大边差值”的形式出现。处理它的时候最常见的手段不是直接计算而是把坐标做伸缩。因为max(|dx|,|dy|)里带一个max没法直接拆成两个独立项但如果把坐标轴旋转45度max就会被“打开”成两个绝对值的和这就是曼哈顿距离。反过来说曼哈顿距离里带一个加号不好分别处理两个方向但换到新坐标系后加号会变成max。理解了这一点就明白为什么那么多题解里会出现“把点变成(xy, x-y)”这个操作了。它不是魔法只是换了一把尺子。同一组点换了坐标系之后距离表达式变简单了覆盖关系也变得更直观。这里说的“坐标系移动”不单单指平移还包括旋转和缩放。2.2 旋转45度的坐标系移动到底在做什么想象一张透明的坐标网格纸。你把它以原点为中心旋转45度再按比例缩小原来的横平竖直街道就变成了斜向街道。点还是那些点物理位置没变但它们在网格纸上的读数变了。这才是“坐标系移动”的本质不是移动物体而是换个角度看。具体到公式给定原始坐标(x,y)定义新坐标u x yv x - y这个变换的几何效果是把原坐标轴旋转45度并且整体放大了sqrt(2)倍。两个点之间的曼哈顿距离|dx||dy|在新的(u,v)坐标系里恰好等于切比雪夫距离。这个恒等式是这套解法的地基值得亲手推一遍。用分类讨论证明很简单。设adx,bdy。如果a和b同号那么|ab| |a||b|而|a-b| |a||b|所以max(|ab|, |a-b|) |a||b|。如果a和b异号那么|a-b| |a||b|而|ab| |a||b|结果一样。因此|dx| |dy| max(|dxdy|, |dx-dy|)这就证明了一个点P到候选中心C的曼哈顿距离等于变换后两点在(u,v)坐标下的切比雪夫距离。2.3 两个方向的转换公式表这个变换不是单向的反过来也能用。如果题目给的是切比雪夫距离想把它转成曼哈顿距离可以用类似方式定义u(xy)/2,v(x-y)/2。因为缩放比例会影响数值我把两组常用转换整理成表格原度量坐标变换新度量说明曼哈顿距离 dxdy切比雪夫距离 max(dx,dy第一行是这一题的核心。第二行也有用比如有些题给的是切比雪夫距离但需要套曼哈顿距离才会算的二维前缀和。两张表不需要硬背记住一个原则曼哈顿的“绝对值之和”对应新坐标系里的“绝对值最大项”切比雪夫的“最大值”对应新坐标系里的“绝对值之和”。这个关系就像把不等式里的max和加法互换。3. 核心变换从最大曼哈顿距离到最小方形覆盖3.1 把目标函数改写成切比雪夫形式现在把原题的目标函数完整写一遍。设所有点为(xi, yi)候选中心为(cx, cy)目标函数是F max_i ( |xi-cx| |yi-cy| )用上面证明的恒等式对每个点有|xi-cx| |yi-cy| max( |(xiyi)-(cxcy)|, |(xi-yi)-(cx-cy)| )定义ui xi yivi xi - yicu cx cycv cx - cy于是原目标函数变成F max( max_i |ui-cu|, max_i |vi-cv| )这一步非常关键因为它把一个二维耦合问题拆成了两个独立的一维投影问题。原坐标系下的曼哈顿距离是两个分量相加x方向的偏差和y方向的偏差会互相影响但在新的(u,v)坐标系下切比雪夫距离只看每个维度各自的偏差取最大值两个坐标轴彻底解耦。3.2 为什么变换后问题会独立成两个维度切比雪夫距离有一个让人舒服的性质max_i max(|du_i|, |dv_i|)等于max( max_i |du_i|, max_i |dv_i| )。也就是说“先对每个点看两个方向谁更大再对所有点取最大”等价于“先按u方向对所有点取最大再按v方向对所有点取最大最后比较”。交换了max的嵌套顺序代价没有变。换一个更直观的说法在(u,v)坐标系里要找的其实是“最小半径R的轴对齐正方形能覆盖所有变换后的点”。这个正方形的u方向只需要考虑所有点u坐标的跨度v方向只需要考虑所有点v坐标的跨度。两个方向互不干扰可以单独算最优半径再取较大者作为整体半径。这正是“最小方形覆盖”问题的标准形态。切比雪夫距离的单位圆是轴对齐正方形所以“最大化距离最小化”在这里转化成“要盖住所有点正方形半边长最少是多少”。这个几何图像一旦建立答案几乎可以一眼看出来。3.3 最优中心与半径怎么取单独看u方向。假设一堆点的u坐标最小值是minU最大值是maxU。为了覆盖这两个端点中心cu到其中任意一个的最远距离至少是(maxU - minU)/2。取cu (minU maxU)/2时所有点的u方向偏差都不超过这个值所以这一维的最优半径是Ru (maxU - minU) / 2v方向同理Rv (maxV - minV) / 2全局最小最大距离就是两者中较大的answer max(Ru, Rv) max(maxU-minU, maxV-minV) / 2为什么这里可以用中点而不是中位数因为问题是最大值最小不是总和最小。中位数均衡的是点的数量无法保证“离中心最远的点”不会太远而中点直接压住了跨度。拿一维点[1,2,100]说中位数中心2对应的最大距离是98中点中心51.5对应的最大距离只有48.5。只要允许中心是实数中点就是最优解。这里有一点值得注意最优中心的cu不一定要取唯一值。只要cu落在[minU, maxU]的中点附近并且v方向也满足类似条件整体半径都能达到最优。具体实现时取中点最省事反变换也最对称。3.4 反变换回原坐标系题目要的是原坐标系里的中心点(cx, cy)而我们的最优解算出来的是(cu, cv)。反变换公式直接从定义解出来cx (cu cv) / 2cy (cu - cv) / 2用样例(0,0), (1,1), (2,0)走一遍。三个点的u分别是0、2、2v分别是0、0、2。于是minU0maxU2minV0maxV2。最优半径是max(2,2)/21。中心cu1,cv1反变换得到cx1,cy0正好是前面手动找出的最优中心(1,0)。原坐标下中心点可能出现小数比如1.5这是允许的。如果题目强制中心必须是整数格点那么答案要上取整中心可以在中点附近枚举几个整数点取最优。这个细节我在第四节会专门展开。4. 完整代码、调试样例与常见错误速查4.1 可直接跑的Python实现整套算法的代码非常短核心只有几行。时间复杂度是O(n)空间O(1)对所有点的u、v分别维护最小值和最大值即可def solve(points): min_u min_v float(inf) max_u max_v float(-inf) for x, y in points: u x y v x - y if u min_u: min_u u if u max_u: max_u u if v min_v: min_v v if v max_v: max_v v # 半径新坐标系下切比雪夫距离的一半跨度 ans max(max_u - min_u, max_v - min_v) / 2.0 # 新坐标系下的最优中心 cu (min_u max_u) / 2.0 cv (min_v max_v) / 2.0 # 反变换回原坐标 cx (cu cv) / 2.0 cy (cu - cv) / 2.0 return ans, (cx, cy)调用方式很简单pts [(0, 0), (1, 1), (2, 0)] ans, center solve(pts) print(ans, center) # 1.0 (1.0, 0.0)这里需要注意u和v都可能超过原始坐标的范围比如坐标在1e9量级时u、v会到2e9。用Python不用担心溢出但用C时一定要开long long否则跨度计算会直接爆掉。这个坑我在竞赛里见过不少次。4.2 用暴力对拍验证正确性写完正解之后我习惯写一个暴力版本做随机对拍尤其是这种带坐标变换的题目容易在某一步把公式记翻。暴力做法是枚举候选中心检查所有点到它的曼哈顿距离最大值。因为中心可以是任意实数实际对拍时把中心限制在整数格点上再配合随机小数据就足够发现公式错误了。import random def brute(points): xs [p[0] for p in points] ys [p[1] for p in points] best float(inf) best_center None for cx in range(min(xs) - 1, max(xs) 2): for cy in range(min(ys) - 1, max(ys) 2): cur max(abs(x - cx) abs(y - cy) for x, y in points) if cur best: best cur best_center (cx, cy) return best, best_center for _ in range(10000): n random.randint(1, 8) pts [(random.randint(-5, 5), random.randint(-5, 5)) for _ in range(n)] ans1, _ solve(pts) ans2, _ brute(pts) if abs(ans1 - ans2) 0.5: print(mismatch, pts, ans1, ans2) break这里比较时用了0.5的容差因为暴力限制整数中心而正解允许实数中心两者最多差0.5左右。实际跑下来如果公式没写错10万组随机数据也不会有问题。这个对拍脚本每次写新题我都会复用能省下大量人工造样例的时间。4.3 为什么答案和坐标绝对值无关一个容易忽略的细节是答案只由u、v的跨度决定和点的绝对位置无关。把所有点整体平移同样距离仓库选址问题的答案不会变因为相对位置完全一样。这在业务上也好理解整个城市坐标平移最远配送距离当然不变。这个性质也能用来做自检。比如把样例每个点都加100(0,0),(1,1),(2,0)变成(100,100),(101,101),(102,100)用solve算出来答案仍然是1.0中心变成(101,100)。如果计算结果出现变化说明变换公式里混入了不该有的常数项比如在u或v上多加了偏移量。另外u和v的跨度还有一个几何解释maxU-minU和maxV-minV分别对应点集沿两条45度斜线的投影长度。这两个投影长度中的较大者除以2恰恰就是曼哈顿距离意义下的最小最大距离。理解这一点之后很多变体题都能直接套。4.4 常见错误排查表我把这个题在调试中容易踩的坑整理成一张表几乎每一条都有同学在群里问过错误现象错误原因正确做法答案比预期大且中心是原坐标中位数把“距离和最小”的中位数思路错用在“最大值最小”上中心改为min、max的中点输出中心和答案相差固定倍数忘了uxy, vx-y自带的sqrt(2)缩放影响按跨度差直接除以2不要额外缩放反变换算出来的cx、cy偏差很大只算了cu、cv忘记反解回原坐标用cx(cucv)/2, cy(cu-cv)/2整数中心题目答案不对允许任意实数中心直接输出小数对半径上取整并枚举中点附近几个整数点C程序大样例溢出没考虑u、v的绝对值超过原坐标范围坐标开long long跨度计算避免先乘后除只算max(minX,maxX)或max(minY,maxY)漏掉45方向投影以为两个方向就是x、y必须先转(u,v)再取两个方向跨度这些坑里最隐蔽的是“整数中心”那一条。如果业务要求仓库必须落在某个格点上最优中心附近可能有多个候选点需要枚举。一般做法是先算出实数中心再把它上下取整组合出四个候选点分别计算最大距离取最小值。它对应的最小最大距离可能比实数解大0.5所以输出时要用math.ceil。5. 这个套路还能用到哪些题目上5.1 最小包围正方形与旋转45度扩展原题的曼哈顿最大值最小化本质上是在原坐标系里找一个斜45度的正方形去覆盖所有点正方形的边和曼哈顿“单位圆”的边缘平行。做完坐标变换之后正方形边变成轴对齐于是求最小边长变成算两个方向的跨度。如果题目本身给的就是切比雪夫距离要你找一个轴对齐正方形覆盖点集那甚至不需要换坐标直接用原坐标的max(maxX-minX, maxY-minY)/2就是答案。如果允许正方形旋转任意角度问题会变得更难一些但枚举凸包上的边方向加旋转卡壳也能处理。练题时可以先从0度和45度两个特例入手感受坐标系移动带来的简化效果。5.2 反过来用切比雪夫转曼哈顿的典型场景有一类题给的是两个点的切比雪夫距离但要统计“距离小于等于R的点对数量”。如果直接在切比雪夫定义下算需要二维树状数组或者容斥比较麻烦。这时候反过来用u(xy)/2, v(x-y)/2变换切比雪夫距离会变成曼哈顿距离而曼哈顿距离可以拆成四个方向的偏序关系再用排序和树状数组解决。其实很多“旋转坐标系”的经典题都在玩这个互换。比如给定若干点按曼哈顿距离求最近点对直接排序xy、x-y可以降低复杂度又比如判断“是否存在一个点使它到所有点的切比雪夫距离都不超过R”可以转换为检查u、v两个维度的跨度是否都小于等于2R。题目包装千变万化核心恒等式只有一个。5.3 两个中心和多目标扩展思路如果题目变成要选两个仓库让所有点到最近仓库的最大曼哈顿距离最小简单公式就不存在了。但解法思路还是顺着坐标变换走先转成(u,v)切比雪夫距离然后二分答案R检查能否用两个轴对齐正方形覆盖所有点。检查函数可以用扫描线按u排序枚举左侧一个正方形覆盖前缀点右侧覆盖后缀点。更高维的情况也有类似技巧三维切比雪夫距离可以线性时间求最小覆盖立方体半径公式就是三个维度跨度分别中点。不过高维曼哈顿转切比雪夫就不是每个方向都那么简单涉及线性代数里的情况。日常刷题先把二维的二维变化玩熟很多三维题会在二维的基础上套一层前缀和。我自己每次遇到坐标变换题都会先在草稿纸上画一个坐标轴手动把(0,0)、(1,1)、(2,0)这三个点代入公式验证一遍。这个只有三行的手算过程是防止“公式记反”最有效的方法。另外写代码时也建议用一个断言函数计算最终中心到每个点的曼哈顿距离并和答案比较一旦出现偏差立刻暴露问题。这题做完之后最大的收获不是记住这个公式而是意识到“距离”不是一个固定的东西换一个坐标系看问题很多看似复杂的优化目标会自然坍缩成简单的覆盖问题。把L1和L∞之间的这层关系想明白以后遇到任何带曼哈顿或切比雪夫的题目都能多一条清晰的解题路径。