★ FEATURED ARTICLE 1. 题目拆解从“按顺序访问所有点”读出的三个隐藏信息LeetCode 1266 全称是 Minimum Time Visiting All Points中文一般叫“访问所有点的最小时间”在热门 100 题里属于那种“一看就会、一写就对、但一深问就卡壳”的题目。题面特别朴素给你一个二维数组 points表示平面上按顺序排列的点你从第一个点出发每秒可以沿水平、垂直或对角线方向移动一个单位问按顺序访问完所有点的最短总时间是多少。先别急着写循环。这个题目至少藏着三个信息读不出来后面很容易用错模型。第一顺序是硬约束。points[i] 和 points[i1] 的访问顺序已经定死你不能中途绕路去“顺便”访问后面的点再折回来。也就是说这不是旅行商问题不需要求点的遍历顺序只需要把相邻两点之间的移动时间全部累加。第二“每秒移动一个单位”不等于“只能走上下左右”。很多人做这种题目条件反射用曼哈顿距离但那是在只能四方向移动的棋盘规则下才成立。1266 明确说了对角线也能走而且对角线同样耗时 1 秒。这一条是整个题目的命门后面我专门讲为什么。第三题目考的不是模拟而是距离度量的选择。如果把每个点对之间的路径真正一步步模拟出来代码会很丑而且容易错。最优解本质上是在问你在允许斜着走的平面里两点之间最少要几步答案不是两点间直线距离也不是横纵坐标差之和而是切比雪夫距离。这个点能想明白代码就是三行的事。适合拿这个题练手的人主要有三类刚刷题不久、想建立“距离度量”概念的初学者准备面试、想用一个简单题串讲数学原理的候选人以及写业务代码写久了、想找回算法手感的老兵。它属于那种“五分钟做完、五十分钟讲透”的题用来做面试热身或者新手入门都相当合适。2. 两点之间的最短时间为什么是 max(|dx|, |dy|)直观推导2.1 先拿一个具体例子试算假设你从 A(3, 4) 出发要去 B(6, 1)。横坐标差了 3纵坐标差了 -3也就是 dx3, dy-3。如果只能上下左右走最少步数是 |dx| |dy| 6这就是曼哈顿距离。但题目允许对角线意味着你可以同时“消掉”一个横向步和一个纵向步。每一步如果走对角线横纵坐标各变化 1方向任意那么走 3 步对角线之后你已经从 (3,4) 到了 (6,1)。3 步就到而不是 6 步。为什么不是更少因为你横坐标必须从 3 变到 6总共变化量是 3。哪怕每一步都走对角线每步最多让横坐标变化 13 步已经是最极限了。同理纵坐标变化量也是 33 步也够。在这个例子里两个方向的变化量恰好相同所以答案就是 3。换一组数再看。从 A(1, 1) 到 B(5, 3)dx4, dy2。你能先走 2 步对角线把横纵坐标变成 (3,3)此时纵向已经到位横向还剩 2 个单位。余下的 2 步只能水平走总计 224 步。这个 4 恰好等于 max(4, 2)。2.2 三种“距离度量”的对比为什么对角线改变了游戏规则同一组点对选不同的移动规则答案完全不同。我把三种常见距离列在这儿方便对比着看移动规则距离公式例从(1,1)到(5,3)适用场景只能上下左右曼哈顿距离abs(dx) abs(dy)6棋盘格、城市街区任意方向直线欧氏距离sqrt(dx² dy²)约4.47物理直线最短路径水平/垂直/对角线切比雪夫距离max(abs(dx), abs(dy))4国际象棋王走法、本题目关键就在欧氏距离那一行。数学上两点之间最短的路径当然是直线但题目要求你“每秒移动一个单位、方向只能是水平/垂直/对角线”对角线本身就是合法的 45 度斜线所以你在离散栅格里能走出来的最短步数不是欧氏长度而是“用斜线尽量抵消两个方向的差距”。切比雪夫距离本质上是“在 8 连通网格上的最短路径长度”而 1266 的移动规则正是 8 连通。这也是为什么很多人第一次做这道题会直觉想到 sqrt(dx*dx dy*dy)然后提交发现答案对不上。因为题目要的是“步数”不是“长度”你不可能走半格的。2.3 严格的数学证明两步夹逼光有直觉不够面试被追问的时候最好能给出一个两段式的论证。先证明最少步数不可能小于 max(|dx|, |dy|)。无论你怎么走每步最多让你的横坐标变化 1要走完 |dx| 的横差至少要 |dx| 步同理至少要 |dy| 步。所以总步数必须同时大于等于这两个数即步数 ≥ max(|dx|, |dy|)。再证明这个下界一定可以达到。假设 dx dy 0其他情况通过翻转坐标轴完全对称。先走 dy 步对角线此时横纵坐标差距都减少了 dy剩下的横向差距是 dx - dy再走 dx - dy 步水平方向。总步数是 dy (dx - dy) dx max(|dx|, |dy|)。如果 dy 是负数把“对角线”换成另一个方向的斜线即可结论完全一样。这个证明把“能不能达到”和“不能再少了”都堵死了逻辑闭环。平时写题可以不用写这么细但脑子里要有这条链面试讲思路时一说出来层次会完全不一样。3. 代码实现三行核心逻辑与三种语言写法3.1 核心逻辑相邻点对求和整个题目的算法骨架就一句话把 points 里相邻两个点的切比雪夫距离依次累加。累加背后隐藏着一个看起来理所当然但值得点破的前提——路径可叠加性。你从 P0 走到 P1 需要 d1 步从 P1 走到 P2 需要 d2 步那么从 P0 经过 P1 再到 P2总步数就是 d1 d2。因为 P1 是中间点前一段的终点就是后一段的起点时间消耗直接相加不存在互相抵消或重叠的空间。这一点保证了“逐对求和”是正确的不需要考虑任何跨点对的优化。3.2 C 实现C 写起来最直接需要注意头文件包含 和 或 获取 abs 函数。class Solution { public: int minTimeToVisitAllPoints(vectorvectorint points) { int ans 0; for (int i 1; i points.size(); i) { int dx abs(points[i][0] - points[i - 1][0]); int dy abs(points[i][1] - points[i - 1][1]); ans max(dx, dy); } return ans; } };这段代码用到了 abs 和 max分别来自 和 。在 LeetCode 的编译环境里bits/stdc.h 通常会帮你隐式带上这些头文件本地编译器不一定。所以我建议自己写的时候显式包含 和 避免本地能过、提交也过但换个环境就报编译错。3.3 Python 实现Python 的写法可以非常紧凑读起来也直观。用 zip 把相邻点配对循环里直接解包。class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: ans 0 for (x1, y1), (x2, y2) in zip(points, points[1:]): ans max(abs(x2 - x1), abs(y2 - y1)) return anszip(points, points[1:]) 这个习惯写法很实用。points[1:] 会把第一个点去掉然后 zip 逐对配对天然形成 (P0,P1), (P1,P2), ... 的相邻序列。注意这里 points 的长度至少为 1题目已经保证不必额外判空。如果非要一行秀可以这样写class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: return sum(max(abs(p2[0] - p1[0]), abs(p2[1] - p1[1])) for p1, p2 in zip(points, points[1:]))这版用了生成器表达式配合 sum逻辑没变纯粹是代码风格上的差异。我个人更推荐前面那个显式循环的版本因为调试的时候可以在循环里加断点方便观察每一对的 dx、dy 到底是多少。3.4 JavaScript 实现JS 的数组解构和 Math API 组合起来也很顺var minTimeToVisitAllPoints function(points) { let ans 0; for (let i 1; i points.length; i) { const dx Math.abs(points[i][0] - points[i - 1][0]); const dy Math.abs(points[i][1] - points[i - 1][1]); ans Math.max(dx, dy); } return ans; };JavaScript 里没有内置的 abs 操作符必须走 Math.abs这个没什么可省的。另外 points.length 在循环条件里每次都会读取性能无伤大雅但如果想让代码更有“性能洁癖”可以在外面 let n points.length 缓存一下。3.5 复杂度分析时间上只需要扫描一次 points 数组时间复杂度 O(n)n 是点个数。空间上只用了常数个变量O(1)。这个题数据范围一般不会很大但就算给你十万个点这个算法也是毫秒级跑完没什么可优化的空间。值得一提的是不需要处理“多个点同时访问”的情况。题目是按顺序一个一个访问点点本身不占时间只有移动才占时间所以每个点对之间的距离全部加总就是答案。如果你上网搜题解偶尔会看到有人讨论“路径交叉能不能省时间”那属于把条件改成了“允许不按顺序访问”和 1266 原题完全不是一回事。4. 提交出错的四种常见场景这些坑我基本都踩过这个题虽然标着 Easy但我在给同事讲题和看社区题解时发现错误率比想象中高。错误集中在四种情况对照着检查基本能覆盖所有提交失败的原因。4.1 把“对角线移动 1 秒”做成 sqrt(2)有人看到“可以沿对角线移动”心里默认对角线一步等于欧氏距离的 sqrt(2)于是写出了诸如 ans Math.sqrt(dxdx dydy) 的代码。这个写法在“任意方向移动且按路程计费”的模型下是对的但题目计时是按“步数”而不是“路程”。对角线一步就是 1 秒不乘根号二也不做浮点运算。如果拿浮点距离去求和还会引入精度问题。比如 sqrt(164) ≈ 4.47累加几次之后出现 0.000001 级别的误差虽然 LeetCode 对 int 返回类型会直接要求你转成整数但用浮点到头来四舍五入在不同测试用例下很容易差 1。我在讨论区确实见过有人因为这个卡了半天最后把公式换成 max 才恍然大悟。4.2 把“每个点本身”当成了要额外计时的对象这个坑比较隐蔽。有人在循环里写的是ans max(dx, dy) 1;加 1 的理由是“访问这个点也要花时间”。但题目计时的是移动不是访问。点只是坐标到了就算访问完成不需要额外停留一秒。这样每个点对都会多加 1导致结果比答案大 n-1。我当时第一次做这个题也犯过类似的错误但不是在这里而是把 points.size() 当成“要访问的点数”在循环外部额外处理了最后一个点。后来一想最后一个点根本不需要“处理”你到它那儿就结束了没有需要移动的下一个目标。凡是把“最后一个点”单独拎出来加时间的都是在给不存在的路程付款。4.3 用曼哈顿距离代替切比雪夫距离这是最高频的错法尤其是有棋类游戏经验的人。国际象棋里的车走上下左右所以车从 A 到 B 的步数是曼哈顿距离王可以走斜线所以王的步数是切比雪夫距离。如果你把 1266 想成“只能上下左右走”自然会写出 ans abs(dx) abs(dy)结果偏大。具体偏大多少偏大的部分恰好是 min(|dx|, |dy|)因为你原本可以用 min(|dx|, |dy|) 步对角线路程同时消掉两个方向的差距曼哈顿模型把这段斜线硬拆成了两段正交路程白白多算了。所以正确代码里 max(dx, dy) 和错误代码里的 dx dy差的正是 2 * min(dx, dy) 的一半数量级——等等准确说是 dxdy 比 max 多出 min(dx,dy)也就是每一对点你多算了一段路。4.4 坐标差计算方向写反导致负数没有取绝对值把 points[i] 和 points[i-1] 的顺序搞反不会影响绝对值的大小但如果没有用 abs 包装某些语言里负数相加就会把答案算小甚至算成负的。比如 C 里 dx 是 points[i][0] - points[i-1][0]dy 是 points[i][1] - points[i-1][1] 时坐标差可能为负此时你用 max(dx, dy) 取到的可能是负值或一个绝对值更大的负值最后 ans 会出现负数提交直接报错。这个坑常见于从“前一个点减后一个点”改写成“后一个点减前一个点”时漏掉了 abs。只要统一用 abs 包好怎么写都不会错。我把这四种情况整理成一张自查表提交前对照一遍基本稳了错误类型错误公式正确公式典型误判点浮点对角线sqrt(dx² dy²)max(dx, dy)把步数当路程给点计时max(dx, dy) 1max(dx, dy)把访问当消耗曼哈顿dx dymax(dx, dy)忽略斜线一步走双方向少绝对值max(dx, dy)max(abs(dx), abs(dy))坐标差为负5. 从 1266 延伸三个值得思考的变体方向5.1 变体一上下左右四方向移动如果把移动规则改成只能沿水平或垂直方向移动这个题的答案就从切比雪夫距离变成曼哈顿距离。这个变体的典型代表是 LeetCode 上不少模拟题比如热门讨论里常见的“爱吃香蕉的狒狒”那类题——虽然那是二分查找主题不是距离问题但同样考察对“移动规则”的精确理解。具体到代码只需要把 max(dx, dy) 改成 dx dy。很多人会觉得这只是改一个函数的事没什么值得练的。但我建议你亲手写一遍并且尝试画出同一组点在下图两种规则下的不同轨迹感受一下“规则决定距离度量”这件事。这是建立算法直觉的好方法。5.2 变体二不限制访问顺序求最短路径如果把“按顺序访问”这个约束去掉问题性质就完全变了。任意两点之间依然可以用切比雪夫距离度量但你需要在所有点之间选择一个访问顺序使总路径最短。这就是一个典型的旅行商问题暴力枚举是 O(n!)n 稍微大一点就爆了。即便用状态压缩动态规划复杂度也是 O(n² * 2^n)只适用于 n 20 左右的小数据。从 1266 的 O(n) 直接跳到这个 NP-hard 变体会让你直观感受到“顺序约束”对问题难度的巨大影响。这也是面试官很喜欢的追问方式先给你一个 Easy 题然后问“如果允许随便排序呢”。这时候你需要判断出它是 TSP而不是天真地以为贪心就近访问就行。事实上在切比雪夫距离下就近贪心都不保证最优很容易举出反例。5.3 变体三三维空间推广把平面点推广成三维点 (x, y, z)移动规则变成可以沿任意坐标轴或空间对角线移动一步每步耗时 1 秒。那么两点之间最短步数是多少答案是 max(|dx|, |dy|, |dz|)。推导方式和二维完全一致每个坐标方向每步最多变化 1所以步数不能小于最大的那个变化量而你可以先走若干步空间对角线把最大的坐标差消到和第二大相等再把第二大的消到和最小相等最后补齐剩余差距。这个推广在 LeetCode 上不多见但做机器人三维路径规划时这种度量是实打实会遇到的。顺着这个思路继续想如果每步能走的坐标增量不是“0 或 1”而是一个集合比如可以走骑士步那就变成更复杂的组合问题需要用 BFS 或图论建模。1266 只是这条长线中最简单的锚点。6. 最后分享一点实际体会这个题我讲过好几次也在面试中问过候选人。让我印象很深的是很多候选人能在五分钟内写出正确答案但当我追问“为什么是 max 而不是 sum”时会沉默一会儿。这恰恰说明刷题不能只看 AC要把公式背后的移动模型吃透。你如果能用自己的话把“对角线一步同时推进两个方向所以短板靠长板补齐”这个道理讲清楚才算真正拿下这个题。一个小技巧把 max(abs(dx), abs(dy)) 记成“8 连通网格上的最短步数”以后遇到国际象棋王走法、像素画线、机器人八方向寻路你都能直接套用。这个公式在图形学和路径规划里出现频率极高不只是刷题用得上。下次再看到“访问所有点的最小时间”这类题先问自己一句这里的移动规则允许对角线吗答案一确定距离公式也就跟着确定了剩下的只是循环求和。
阅读完成 · 觉得有帮助？
