企业官网建设流程全解析

1. 题目拆解：从“按顺序访问所有点”读出的三个隐藏信息

LeetCode 1266 全称是 Minimum Time Visiting All Points，中文一般叫“访问所有点的最小时间”，在热门 100 题里属于那种“一看就会、一写就对、但一深问就卡壳”的题目。题面特别朴素：给你一个二维数组 points，表示平面上按顺序排列的点，你从第一个点出发，每秒可以沿水平、垂直或对角线方向移动一个单位，问按顺序访问完所有点的最短总时间是多少。

先别急着写循环。这个题目至少藏着三个信息，读不出来，后面很容易用错模型。

第一，顺序是硬约束。points[i] 和 points[i+1] 的访问顺序已经定死，你不能中途绕路去“顺便”访问后面的点再折回来。也就是说，这不是旅行商问题，不需要求点的遍历顺序，只需要把相邻两点之间的移动时间全部累加。

第二，“每秒移动一个单位”不等于“只能走上下左右”。很多人做这种题目条件反射用曼哈顿距离，但那是在只能四方向移动的棋盘规则下才成立。1266 明确说了对角线也能走，而且对角线同样耗时 1 秒。这一条是整个题目的命门，后面我专门讲为什么。

第三，题目考的不是模拟，而是距离度量的选择。如果把每个点对之间的路径真正一步步模拟出来，代码会很丑，而且容易错。最优解本质上是在问你：在允许斜着走的平面里，两点之间最少要几步？答案不是两点间直线距离，也不是横纵坐标差之和，而是切比雪夫距离。这个点能想明白，代码就是三行的事。

适合拿这个题练手的人主要有三类：刚刷题不久、想建立“距离度量”概念的初学者；准备面试、想用一个简单题串讲数学原理的候选人；以及写业务代码写久了、想找回算法手感的老兵。它属于那种“五分钟做完、五十分钟讲透”的题，用来做面试热身或者新手入门都相当合适。

2. 两点之间的最短时间为什么是 max(|dx|, |dy|)：直观推导

2.1 先拿一个具体例子试算

假设你从 A(3, 4) 出发，要去 B(6, 1)。横坐标差了 3，纵坐标差了 -3，也就是 dx=3, dy=-3。

如果只能上下左右走，最少步数是 |dx| + |dy| = 6，这就是曼哈顿距离。但题目允许对角线，意味着你可以同时“消掉”一个横向步和一个纵向步。每一步如果走对角线，横纵坐标各变化 1（方向任意），那么走 3 步对角线之后，你已经从 (3,4) 到了 (6,1)。3 步就到，而不是 6 步。

为什么不是更少？因为你横坐标必须从 3 变到 6，总共变化量是 3。哪怕每一步都走对角线，每步最多让横坐标变化 1，3 步已经是最极限了。同理，纵坐标变化量也是 3，3 步也够。在这个例子里，两个方向的变化量恰好相同，所以答案就是 3。

换一组数再看。从 A(1, 1) 到 B(5, 3)，dx=4, dy=2。你能先走 2 步对角线，把横纵坐标变成 (3,3)，此时纵向已经到位，横向还剩 2 个单位。余下的 2 步只能水平走，总计 2+2=4 步。这个 4 恰好等于 max(4, 2)。

2.2 三种“距离度量”的对比：为什么对角线改变了游戏规则

同一组点对，选不同的移动规则，答案完全不同。我把三种常见距离列在这儿，方便对比着看：

关键就在欧氏距离那一行。数学上两点之间最短的路径当然是直线，但题目要求你“每秒移动一个单位、方向只能是水平/垂直/对角线”，对角线本身就是合法的 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(vector<vector<int>>& 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 ans

zip(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(16+4) ≈ 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) 的一半数量级——等等，准确说是 dx+dy 比 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 包好，怎么写都不会错。

我把这四种情况整理成一张自查表，提交前对照一遍基本稳了：

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 连通网格上的最短步数”，以后遇到国际象棋王走法、像素画线、机器人八方向寻路，你都能直接套用。这个公式在图形学和路径规划里出现频率极高，不只是刷题用得上。下次再看到“访问所有点的最小时间”这类题，先问自己一句：这里的移动规则允许对角线吗？答案一确定，距离公式也就跟着确定了，剩下的只是循环求和。