企业官网建设流程全解析

LeetCode 1266，题目标的是【简单】，可我刚看到“访问所有点的最小时间”这几个字，下意识以为是道图论或者动态规划题。读完约束才发现，最大的点才100个，坐标也就是正负一万，这题能难到哪去？但真正让我卡住片刻的不是写代码，而是想通一件事：为什么相邻两点之间的耗时，不是直线距离，而是横纵坐标差里那个较大的数。如果你也在这道题上转过弯来，或是对“对角线移动”三个字理解得模模糊糊，那这篇文章应该能帮上忙。我会把题目规则、数学推导、代码实现、常见坑点完整拆一遍，最后再聊聊把题改成“任意顺序访问”或“只能上下左右走”之后，答案会怎么变。

1. 这道题到底在问什么：先别急着写代码

很多朋友看到“最小时间”就条件反射地打开BFS模板，实际上这题不需要任何搜索算法。我们先把规则读清楚，因为90%的误解都出在审题环节。

1.1 题目重述：按数组顺序访问点

输入是一个二维数组points，里面每个元素是[xi, yi]，表示平面上的一个点。比如[[0,0],[1,1],[2,2]]就是三个点，我们要从points[0]出发，按顺序访问points[1]、points[2]，一直到最后。注意两点：

• 访问顺序已经固定，就是数组下标顺序，不存在“我先去离我近的那个点”这种优化空间。
• 不需要回到出发点，走完最后一个点就结束。

这个“顺序固定”和“不用回来”是两个很容易被忽略的前提。我见过有人把题目理解成“从第一个点出发，访问完所有点后还要回到起点”，最后答案多算了一段距离，白白错一次。

1.2 “对角线移动”意味着什么：这就是国王走法

规则里最关键的一句是：从一个点移动到另一个点，可以水平、垂直或对角线移动一个单位长度，每次耗时1秒。

什么叫对角线移动？就是横坐标变1、纵坐标也变1，比如从(0,0)走到(1,1)，一步到位，耗时1秒。如果只允许水平垂直走，这一步得先向右再向上，花2秒。“对角线”三个字，让这个问题的度量方式彻底变了。

国际象棋玩家看到这里应该秒懂：这跟“王”（King）的走法一模一样。王每次可以走周围8个方向中的任意一格，所以从棋盘上任意格子到另一个格子，王需要的最少步数就是max(|Δ行|, |Δ列|)。LeetCode 1266其实就是一个棋盘上按顺序“吃子”的问题。

1.3 看清约束再动手：坐标有正有负，n不超过100

题目约束是n >= 1，n <= 100，坐标范围-10^4 <= xi, yi <= 10^4。

这意味着三件事：

• 坐标可能出现负数，写代码时不要在取绝对值这一步省事。
• 规模极小，哪怕你用BFS硬算每个相邻点也能过，但没必要，后面会看到有O(n)的直接数学解。
• 最大耗时很容易算：相邻点横纵坐标差最大都是2*10^4，最多99段，总耗时不超过2*10^6，int完全够用。但如果题目把坐标范围改得很大，建议直接上long long，省心。

2. 为什么答案是 max(|dx|, |dy|)：切比雪夫距离的直觉与证明

这是整道题的核心。理解了这一层，代码就是一行循环的事。

2.1 先用两个例子感受一下

看示例points = [[0,0],[3,4]]。

• 欧几里得距离是5，但这里能5秒到吗？不能。
• 最优路线是：先沿对角线走3步，从(0,0)到(3,3)，耗时3秒；再竖直向上走1步到(3,4)，耗时1秒。总共4秒。
• 4 =max(|3-0|, |4-0|)=max(3,4)。

再看[[0,0],[1,1],[2,2]]。

• 第一段，从(0,0)到(1,1)，对角线一步直接到，耗时max(1,1)=1。
• 第二段同理，也是1。
• 总耗时2。

如果硬走“左右”或“上下”，会多出不少时间。这就是“对角线同时改两个坐标”带来的优势。

2.2 严密的证明：先找下界，再给出可达方案

设两个相邻点分别是(x1, y1)和(x2, y2)，令dx = |x2 - x1|，dy = |y2 - y1|。

第一步，找下界。每一秒移动，无论你走水平、垂直还是对角线，能让max(dx, dy)减小的幅度最多只有1。为什么？水平移动只减少dx，垂直移动只减少dy，对角线移动同时减少dx和dy各1，但max(dx, dy)这个值的减小量也是1。既然每秒最多只能让较大那个差值减少1，那从max(dx, dy)减到0，至少需要max(dx, dy)秒。所以答案是“不少于max(dx, dy)”。

第二步，证明这个下界能达到。贪心策略：先走min(dx, dy)步对角线，比如dx和dy分别是3和4，就先走3步对角线，把两个差值都变成0和1；之后再沿长轴方向走|dx - dy|步直线，把剩下的差值走完。总步数是：

min(dx, dy) + |dx - dy| = max(dx, dy)

这个等式一眼就能看出来。既然存在一个方案恰好用max(dx, dy)秒，而且任何方案都不可能少于这个数，那最优答案就是它。

提示：这个证明思路比单纯背结论重要。很多人看到“答案是max”就直接开写，但如果面试官追问“为什么”，你得能说出“每秒最多让最大值减1”这个关键观察。

2.3 欧几里得、曼哈顿、切比雪夫：三种距离的对比

这道题的数学本质是切比雪夫距离，也就是L∞范数。我平时刷题习惯把几种距离放在一起对比，这样不容易乱。

LeetCode 1266因为明确允许对角线移动，所以答案就是切比雪夫距离。如果题目改成“只能上下左右”，答案就变成曼哈顿距离的总和。这个区分是后续扩展题的钥匙，后面我会专门讲。

3. 代码实现与复杂度分析：四种主流语言各写一遍

既然公式已经明确，代码就没有任何难度了。核心就一句话：遍历相邻点，累加max(abs(dx), abs(dy))。

3.1 Python：最清晰的版本

class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int: ans = 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]) ans += max(dx, dy) return ans

Python里abs直接能处理负数，max取较大值，代码几乎和公式一一对应。跑示例[[0,0],[3,4]]会返回4。

3.2 C++：刷题主力写法

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; } };

C++注意两点：一是abs对int重载没问题，二是头文件里<cstdlib>或<cmath>提供了整数版本的abs，LeetCode环境默认包含，直接写不会报错。

3.3 Java 与 Go：注意各自 abs 的差异

Java版本：

class Solution { public int minTimeToVisitAllPoints(int[][] points) { int ans = 0; for (int i = 1; i < points.length; i++) { int dx = Math.abs(points[i][0] - points[i-1][0]); int dy = Math.abs(points[i][1] - points[i-1][1]); ans += Math.max(dx, dy); } return ans; } }

Go版本就有点意思了，Go 的math.Abs只接受float64，处理int还得自己写个辅助函数：

func minTimeToVisitAllPoints(points [][]int) int { ans := 0 for i := 1; i < len(points); i++ { dx := abs(points[i][0] - points[i-1][0]) dy := abs(points[i][1] - points[i-1][1]) if dx > dy { ans += dx } else { ans += dy } } return ans } func abs(x int) int { if x < 0 { return -x } return x }

这个细节如果你不提前知道，第一次用Go写很容易卡在类型不匹配上。实际上Go标准库里没有int版的abs，这是个经典“语言特色”，刷题时最好自己备一个工具函数。

3.4 复杂度分析：为什么 O(n) 就是终点

• 时间复杂度：O(n)，每个点只和上一个点比较一次，n最大100，完全无压力。
• 空间复杂度：O(1)，只用几个临时变量。不需要额外数组，不需要visited，不需要队列。

有人可能会问：有没有可能用分治或预处理优化到O(log n)？没必要，因为每个相邻段之间互相独立，必须把每条边的耗时都算进去，信息量本身就是O(n)的。这不像“求区间最大值”之类可以预处理的问题。

提示：面试时建议先说公式和证明，再写代码。这道题真正的考察点是你能不能快速识别出切比雪夫距离，而不是写得一手好循环。

4. 我在提交过程中踩过的坑：题面歧义、边界值与溢出

这道题虽然简单，但坑并不少。我把实际遇到过的和从题解区看到的典型错误整理一下，全是“看着没错，一提交就红”的经典案例。

4.1 老版中文题面的“任意顺序”陷阱

这是最大的一个坑。早期LeetCode中文站翻译这道题时，有一版把英文原文的“visit all the pointsin the order given by points”漏译成了“你可以按任意顺序访问这些点”。

你要是信了这句话，瞬间觉得题目变得巨难：100个点任意顺序访问，求最小时间，这不明摆着是旅行商问题（TSP）吗？NP难那种。你甚至会怀疑LeetCode的难度标签是不是标错了。

实际英文原题一直说的是“按数组给出的顺序访问”，中文版的翻译错误后来修正了。所以如果你在网上看到有人讨论这道题“任意顺序怎么做”，别慌，那是他们读到了旧题面。刷题时如果发现题面疑似有歧义，切到英文原题核对一遍，这个习惯能救命。

4.2 只有一个点的时候，答案是 0

n >= 1，当points只有一个元素时，没有任何移动需要发生，答案是0。我们的代码里循环从i = 1开始，len(points)为1时循环自然不执行，ans就是0，逻辑正确，不用特判。

但有些人会写“从第0个点开始，依次到每个点，最后再回到第0个点”，这会多算一大段。记住：访问所有点，不等于闭合成环。终点就是最后一个点，不需要回来。

4.3 负坐标与 int 溢出：看似安全的边界

坐标范围是-10^4到10^4，两个坐标相减的差的绝对值最大是2*10^4，求和后最多约2*10^6，int肯定够。但我还是建议在正式代码里用long long或者至少心里有数，因为：

• 如果题目后续把坐标范围扩到10^9，差值会达到2*10^9，累加后直接爆int。
• 两个负坐标相减再取绝对值时，如果差值刚好在int上下限附近，某些语言会出现溢出行为。

稳妥的写法是“先转long long再计算”，比如C++里把差值直接赋给long long dx = abs(points[i][0] - points[i-1][0])，虽然答案当前不会超出int，但养成的习惯会在更难的题里保护你。

4.4 各语言 abs 的隐性差异，再提醒一次

• Python 的abs通吃int，没有任何问题。
• C++ 的abs在<cstdlib>和<cmath>里都有整数版本，LeetCode环境没问题，但本地编译有时要#include <cstdlib>。
• Java 的Math.abs对int直接可用。
• Go 的math.Abs只吃float64，int要自己写。

这不算算法坑，但确实会浪费时间。尤其是Go，我第一次提交时直接报错“cannot use abs(points[i][0] - points[i-1][0]) (value of type int) as type float64 in argument to math.Abs”，当时愣了两秒才想起来Go没这接口。

5. 举一反三：如果题目改成“任意顺序”或“只能直走”，答案会怎样

一道简单题的价值，往往在“改条件”之后才体现出来。我刷题时喜欢把题目的限制条件挨个改一遍，看看问题性质怎么变化，这对理解模型非常有帮助。

5.1 允许任意顺序访问：瞬间变成 NP 难问题

如果把“按给定顺序访问”改成“你可以规划任意访问顺序”，问题变成：平面上有n个点，在切比雪夫距离下，找一条经过所有点且总距离最短的路径（不必回到起点）。

这就是经典的旅行商问题（TSP），而且是度量空间下的TSP。n=100时，精确求解只能上状态压缩DP，复杂度O(n²·2^n)，n=20已经到千万级别，n=100基本是天文数字。实际比赛里遇到这种题，要么n很小（比如15以内），要么只能求近似解。

所以LeetCode把这题的顺序定死，其实是把NP难问题降级成了线性问题。“顺序固定”这个条件远比看起来更重要。

5.2 只能上下左右移动：变成曼哈顿距离求和

如果题目去掉“对角线”，只允许水平或垂直移动，那相邻点之间就变成曼哈顿距离dx + dy，总耗时是：

sum(|x[i] - x[i-1]| + |y[i] - y[i-1]|)

拿示例[[0,0],[3,4]]对比就很明显：

• 允许对角线：4秒。
• 只允许横竖：3+4=7秒。

很多网格题都是曼哈顿距离模型，比如计算城市街区里两栋楼之间的步行距离。什么时候用曼哈顿，什么时候用切比雪夫，记住一句话：看移动方向个数，四个方向是曼哈顿，八个方向是切比雪夫。

5.3 旋转坐标系：切比雪夫与曼哈顿的互相转化

这里附加一个数学彩蛋，和本题强相关。

有一个恒等式：

max(|dx|, |dy|) = (|dx + dy| + |dx - dy|) / 2

意思是，切比雪夫距离可以写成旋转45度后的曼哈顿距离的一半。具体来说，把坐标原始差值变换到新坐标系：

u = x + y v = x - y

在这个坐标系里，两点间的曼哈顿距离|du| + |dv|除以2，恰好等于原坐标系下的切比雪夫距离。

这个性质在A*寻路、棋盘问题、图像处理里都有应用。比如你在一个允许八方向移动的格子里做路径规划，有时把坐标旋转一下，计算会变得更规整。知道这个彩蛋，再看这道题就觉得它确实不只是一道“水题”。

6. 这道简单题真正想教会我们的：建模优先，模板靠后

我不知道别人怎么看LeetCode的简单题，但像1266这种题，我刷完的收获比一些中等题还大，因为它逼你从“看到移动就想BFS”的惯性里跳出来。

6.1 从“国王走法”到真实应用场景

“王”的步数公式在实际开发中非常常用：

• 战棋、策略游戏的格子移动，角色一次能走周围8格时，两个格子之间的距离就是切比雪夫距离。
• 网格地图寻路中，如果允许斜着走，启发函数可以用max(|dx|, |dy|)作为代价估计，比曼哈顿距离更准确。
• 机器学习里，L∞范数（切比雪夫距离）用于度量向量各维度差异的最大值，比如某些推荐系统里的相似度计算。
• 图像处理中的八邻域距离，本质也是切比雪夫距离。

这些场景和LeetCode题目一一对应，所以刷题不只是为了面试，也是给以后写工程打底子。

6.2 简单题考的根本是观察力

这道题如果是第一次见，很容易掉进“最短路”的思维定式里。但只要你抓住“对角线每秒同时改两个坐标”这个观察，所有复杂想法都会自动消失。

我在题解区见过有人用BFS逐段跑，虽然也AC了，但代码量是数学解法的好几倍，而且还依赖坐标范围不大这个前提。面试时同样的时间，用公式解法显然更能展示思维质量。

所以我的建议是：看到“移动”“最少时间”“网格”这类词，先别急着敲搜索模板，先把移动规则抄在纸上：

• 四方向 → 曼哈顿距离
• 八方向（含对角线）→ 切比雪夫距离
• 任意方向 → 欧几里得距离

这个条件反射建立起来，很多网格题会省下大量不必要的BFS时间。

6.3 我自己的刷题体会

最后说点个人的东西。我当初刷这道题时，AC只花了不到两分钟，但真正理解“为什么”是在一周之后。当时我在写一个棋盘AI，突然发现算国王步数时顺手就用上了max(|dx|,|dy|)，那一刻才意识到，LeetCode的简单题和真实世界的场景其实是连着的。

如果你想在这道题上多挖一层，可以试试把约束改一改：坐标变成10^9，点数量变成10^5，结论不变，代码依然是O(n)；或者要求“必须经过某些额外点”，那就又不一样了。把一个题目当成一颗种子，在脑子里长出几个变种，是性价比很高的练习方式。

我现在的习惯是，每做完一道简单题，都强迫自己想一想“改了哪个条件就会变难”“这个模型还能用在哪”。这种方法比死磕难题有用得多，毕竟面试时你永远不知道出题人会往哪个方向挖。