看到 LeetCode 1266 这道题的时候我的第一反应是又来一道网格最短路径结果读完题我愣了一下——要求按顺序访问所有点每一步还能斜着走时间统一算 1 秒。这哪是最短路径分明是送分题背后的“距离度量”考点。很多人被“平面点阵”“八个方向”这些词唬住上来就写 BFS 甚至 A*实际上答案就是一个 O(n) 的累加公式所有相邻点的切比雪夫距离之和。这篇文章我会把这道“简单题”掰开揉碎讲清楚。你不需要基础很深跟着我一步步推导从“为什么是 max(|dx|, |dy|)”到三种语言的落地实现再看几个容易 WA 的边界坑最后把它和曼哈顿距离、BFS 这些概念串成一张网。无论你是刚开始刷题的新手还是准备面试想快速过题的老手这篇都能让你少走点弯路。1. 把题目翻译成人话八方向国王走法与大家最容易跑偏的地方1.1 题目到底要我们算什么原题给的输入是一个二维数组points每一个元素是平面上的一个点坐标例如[0, 0]、[1, 1]。要求是从第一个点出发必须按数组顺序依次访问到每一个点最后停在最后一个点上。移动规则是每一步可以从当前点走到八个方向中的任意一个分别是上下左右和四个斜角方向而且不管你这一步是直走还是斜走消耗的时间都是 1 秒。换句话说这就是国际象棋中国王的走法国王每次只能移动一格但八个方向都可以走。那么问题来了从(x1, y1)到(x2, y2)在允许斜走的情况下最少需要多少步题目求的就是把每一段相邻点的最少步数加起来。题目给了一个示例points [[0,0],[1,1],[1,2]]。第一段从(0,0)到(1,1)走一步斜线就到耗时 1 秒第二段从(1,1)到(1,2)只能直着往上走一步耗时 1 秒。总时间是 2 秒。这个例子看着简单但它已经把核心规则讲清楚了斜走和直走等价都能在一步内让两个坐标分量发生大小为 1 的变化。1.2 三个最容易跑偏的思维误区我在评论区见过不少人把这道题想复杂主要跑偏在三个地方第一个误区是看到“点”和“路径”就想到 BFS。实际上这道题没有障碍物也没有“必须经过某条边”的限制。BFS 在这种全连通、等边权的平面里当然能求出正确结果但你会在网格很大的时候白白浪费时间和内存。BFS 是用来处理“有障碍才需要绕路”的这里没有任何障碍数学公式直接秒杀。第二个误区是以为要用欧氏距离向上取整。有人看到两点间直线距离最短就想着sqrt(dx*dx dy*dy)再ceil。这个做法在某些例子上碰巧是对的但只要试一下(0,0)到(3,5)就会发现欧氏距离约等于 5.83向上取整是 6但真实的答案却是max(3, 5) 5因为你先走 3 步斜线到(3,3)再直走 2 步就到(3,5)总共 5 步。那 0.83 的“直线优势”在八方向走法里根本不存在。第三个误区是拿曼哈顿距离来算。曼哈顿距离是“只能上下左右走”的模型公式是|dx| |dy|。但本题允许斜走斜一步能同时消除横向和纵向的差距所以曼哈顿距离会高估真实步数。比如(0,0)到(3,3)曼哈顿距离是 6正确答案是 3。一句话四方向模型用曼哈顿八方向模型用切比雪夫这个对应关系后面会详细说。2. 关键公式还原单段答案是 max(|dx|, |dy|)总答案是逐段累加2.1 先手推两个点对找到感觉假设要从(0,0)走到(3,4)。直观的做法是横着走 3 步再竖着走 4 步总共 7 步。但允许斜走之后你可以先沿对角线方向走 3 步到(3,3)此时横向已经到位竖向还差 1再直着往上走 1 步。总步数是 3 1 4 步。再看另一个点对从(1,1)到(4,5)横向差dx 3纵向差dy 4。先斜走 3 步到(4,4)再竖走 1 步到(4,5)总步数同样是max(3, 4) 4。我整理了几个典型点对方便你对照找规律起点终点dxdy斜走步数直线补步总步数max(dx,dy)(0,0)(3,4)343144(0,0)(3,3)333033(0,0)(5,2)522355(0,0)(7,0)700777规律已经很明显了先斜着走把横向和纵向中较小的那个差值消掉剩下的差距只能直走补齐总步数正好等于较大的那个差值。2.2 下界和构造上界为什么不多不少正是 max要证明这个公式需要从两个方向夹逼。先看下界你每一步最多只能让横向差距减少 1同时纵向差距也最多减少 1。注意“同时”这个限制只在对角移动时成立如果你直着横走纵向差距一点都不会变。所以无论如何横向差距dx需要至少dx步才能清空纵向差距dy需要至少dy步才能清空。总步数不可能小于max(dx, dy)因为连较大的那个差距都还没清完任务不可能完成。再看构造上界假设dx dy那就先走dy步对角线。这dy步会同时让横向差距减少dy、纵向差距减少dy于是纵向清零横向还剩dx - dy。接下来再直走dx - dy步横向全部清零。总步数是dy (dx - dy) dx max(dx, dy)。如果反过来是dy dx对称操作即可先走dx步对角线再直走dy - dx步纵向。下界说“不可能更少”上界说“这个数量一定够”两者一夹结论就是单段最小时间严格等于max(|dx|, |dy|)。这个距离在数学里叫切比雪夫距离也叫棋盘距离因为国际象棋的国王从一格走到另一格最少步数恰好就是这个值。2.3 为什么总答案不是“首尾距离”而是相邻点逐段相加这是很多新手一上来就踩的坑题目要求按顺序访问points的所有点那么总时间到底是不是“从第一个点到最后一个点的距离”不是。如果中间点必须全部经过那么你从第 i 个点出发去第 i1 个点时起始位置已经被上一段卡死了。你不可能跳过中间点也不可能因为后面要走得更远就让前面这段“顺便”变得更短。更严谨地说当前段的最短时间只取决于当前段的起止点终点一旦到达后面所有段的起点就固定了。切比雪夫距离还满足三角不等式这意味着你中途绕去任何其他点再回来只会增加时间不可能减少。所以总时间就是ans Σ max( |points[i][0] - points[i-1][0]|, |points[i][1] - points[i-1][1]| )时间复杂度 O(n)空间复杂度 O(1)一次遍历解决问题。3. 三种语言的实现版本与我在提交时发现的细节坑3.1 Python 版清晰写法与一行流Python 写这段逻辑非常顺手先给一版可读性最高的from typing import List class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: total 0 for i in range(1, len(points)): dx abs(points[i][0] - points[i-1][0]) dy abs(points[i][1] - points[i-1][1]) total max(dx, dy) return total如果你追求极简也可以用生成器一行搞定class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: return sum( max(abs(points[i][0] - points[i-1][0]), abs(points[i][1] - points[i-1][1])) for i in range(1, len(points)) )Python 的abs对int和float都能处理坐标差即便为负也没关系。注意如果points只有 1 个点range(1, 1)是空循环sum 返回 0所以不需要额外特判。3.2 C 版long long 能省掉整型溢出的麻烦C 版本要注意一个细节坐标差值的绝对值可能很大直接abs(points[i][0] - points[i-1][0])在极端数据下可能触发整型溢出尤其是嵌套调用时差值是int先计算再取绝对值。稳妥起见先转long long再算class Solution { public: int minTimeToVisitAllPoints(vectorvectorint points) { long long ans 0; for (size_t i 1; i points.size(); i) { long long dx llabs((long long)points[i][0] - points[i-1][0]); long long dy llabs((long long)points[i][1] - points[i-1][1]); ans max(dx, dy); } return (int)ans; } };这里我用llabs而不是abs因为abs在不同编译器下的重载行为不一致对long long可能产生截断。先强转long long再求差的绝对值是最稳的写法。返回时按题目要求转回int即可。3.3 Java 版Math.abs 的隐藏风险Java 的Math.abs(int)在入参为Integer.MIN_VALUE时会返回负数因为 int 溢出。这道题虽然一般不会给这么大的数但工程习惯上我会用long来承接class Solution { public int minTimeToVisitAllPoints(int[][] points) { long ans 0; for (int i 1; i points.length; i) { long dx Math.abs((long) points[i][0] - points[i - 1][0]); long dy Math.abs((long) points[i][1] - points[i - 1][1]); ans Math.max(dx, dy); } return (int) ans; } }3.4 边界条件和本地测试用例我在本地跑测试时一般会准备这几组数据能覆盖大部分边界逻辑输入预期输出说明[[0,0]]0只有一个点不用移动[[0,0],[0,0]]0两个点重合距离为 0[[0,0],[1,1],[1,2]]2题目自带示例验证规则[[0,0],[3,4]]4斜走 3 步再直走 1 步[[3,2],[-2,2]]5横向差 5纵向差 0答案 5[[0,0],[-3,-4]]4负数坐标不影响绝对值计算这些用例在三种语言里跑出来的结果都应该一致。如果你写完代码直接拿示例提交通过我建议还是自己补一两个极端用例防止某些角落逻辑漏掉。4. 把 1266 装进更大的框架距离度量、BFS 边界和棋盘模型4.1 三种距离公式一张表分清这一题让我想顺便把三种最常见距离梳理一遍以后遇到路径类题目可以直接对号入座距离名称公式生活化类比典型场景欧氏距离sqrt(dx² dy²)鸟可以直接飞过去的最短直线长度几何计算、聚类算法曼哈顿距离|dx| |dy|出租车只能沿着方格街区走不能斜穿四方向网格 BFS、城市街区导航切比雪夫距离max(|dx|, |dy|)国王可以斜走每一步都能同时消掉横向和纵向的差距八方向网格、棋盘移动同一个点对在不同度量下的结果差异很大。比如(0,0)到(3,4)欧氏距离是 5曼哈顿距离是 7切比雪夫距离是 4。你要是拿曼哈顿距离去做八方向移动的题目答案会偏大拿欧氏距离向上取整又会时对时错。只有先把移动规则对应到正确的度量后面才不会白忙。4.2 什么时候 BFS 才是正解公式反而失效这道题能用公式是因为“无障碍 等边权 八方向”三个条件同时成立。如果任何一个条件被破坏公式就不能直接用了。最典型的例子是 LeetCode 1091二进制矩阵中的最短路径。矩阵里有些格子是墙你必须绕开墙从左上角走到右下角虽然它同样允许八方向移动但因为有障碍物你没法保证两个点之间的直线路线一定走得通这时候就得老老实实 BFS。另一个例子是把移动规则改成“只能上下左右”那单段最小时间就变成曼哈顿距离|dx| |dy|总时间也相应改变。我建议你刷完 1266 之后马上把 1091 和 54201 矩阵放在一起做这三个题放在一起能让你彻底分清干净场景用数学公式复杂场景用 BFS启发式搜索里用切比雪夫距离做估价函数。4.3 进阶延伸曼哈顿距离和切比雪夫距离的等价变换如果只刷 1266你不需要知道这个但如果你想在距离类题目上走得更远可以记一个小技巧把坐标系旋转 45 度并缩放曼哈顿距离可以转化为切比雪夫距离。具体做法是令每个点的新坐标为(x y, x - y)那么两个点的曼哈顿距离等于新坐标下的切比雪夫距离。这个变换在处理某些矩阵最远距离问题时非常有用比如让你找一组点中曼哈顿距离最大的两个点直接转成切比雪夫后只需要维护四个极值。现在看不懂也没关系先混个脸熟等刷到相关题再回来看这句话你会感谢自己存过这个知识点。4.4 棋盘模型和寻路系统的实际联系切比雪夫距离并不是只在 LeetCode 里出现。国际象棋里国王从 A 格到 B 格的最少步数就是切比雪夫距离游戏里的 A* 寻路如果允许八方向移动启发函数也经常选切比雪夫距离因为它既能保证 admissible又比欧氏距离更能贴近真实代价。图像处理中做连通域分析时某些形态学操作也把切比雪夫距离当作像素之间的度量。所以别觉得简单题没有价值它背后是一个被反复使用的数学模型。5. 简单题复盘避开三个常见误区沉淀两种解题思路5.1 我在评论区最常见到的三种 WA 原因这道题虽然难度是简单但提交记录里依然能看到不少失败的尝试。我总结了三类高频问题错误原因现象正确做法对首尾两点计算距离忽略了中间点测试用例只给两个点时能过三个点以上就错一定要遍历相邻点对逐段累加用 sqrt ceil 代替切比雪夫某些用例碰巧过直角边差较大时 WA记住八方向移动的准确公式是 max误用曼哈顿距离结果普遍偏大四方向才用曼哈顿八方向用切比雪夫我印象很深的一次是有人用自己的“欧氏距离向上取整”方法跑官方示例居然全对因为示例数据刚好比较“正”。结果一到随机大数据就挂这就是典型的数学建模没建对。写代码之前先花一分钟确定移动规则对应哪种距离度量比什么都重要。5.2 复盘方法把一道简单题改成三个变体我在刷题时有个习惯每做完一道题会尝试改变题目条件看自己还能不能快速给出解法。以 1266 为例我推荐你做三次变体训练第一个变体把移动规则改成只能上下左右。此时答案是所有相邻点曼哈顿距离之和复杂度也是 O(n)。第二个变体在平面上增加一些不可经过的障碍点。此时公式失效需要用 BFS 或 A*而且必须按顺序逐段搜索不能一次性规划全局路径。第三个变体把目标改成“可以任意顺序访问所有点求最短总路径”。这就不是简单题了它直接退化成旅行商问题需要动态规划或搜索。经过这三个变体你对“距离度量”和“路径规划”的边界感会清晰很多。5.3 一个小技巧先证明再提交省下反复 WA 的时间很多简单题大家习惯直接写代码跑但我建议至少在心里做一次“下界 构造上界”的论证。就拿本题来说先想清楚“为什么不可能少于 max”再想清楚“为什么 max 步可以做到”这个论证过程会让你以后再遇到类似题时第一反应不是盲试而是建模。这个习惯对我刷中等题和难题帮助很大因为很多难题卡人的地方就在于缺少这种精细推导。如果你最近也在刷 LeetCode 算法题我建议你把这题和 LeetCode 1091、LeetCode 542 放进同一个收藏夹。当天刷完第二天再把三个题的思路默写一遍。你会发现所谓“简单题”其实是一整类题的地基地基稳了上面盖什么都踏实。