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 1n 100坐标范围-10^4 xi, yi 10^4。这意味着三件事坐标可能出现负数写代码时不要在取绝对值这一步省事。规模极小哪怕你用BFS硬算每个相邻点也能过但没必要后面会看到有O(n)的直接数学解。最大耗时很容易算相邻点横纵坐标差最大都是2*10^4最多99段总耗时不超过2*10^6int完全够用。但如果题目把坐标范围改得很大建议直接上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∞范数。我平时刷题习惯把几种距离放在一起对比这样不容易乱。距离类型表达式几何含义典型场景欧几里得距离sqrt(dx² dy²)两点间直线长度连续平面运动、几何计算曼哈顿距离dx dy只能沿横竖方向走城市街区、四方向网格切比雪夫距离max(dx, dy)允许八个方向走国王走法、八方向网格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 ansPython里abs直接能处理负数max取较大值代码几乎和公式一一对应。跑示例[[0,0],[3,4]]会返回4。3.2 C刷题主力写法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; } };C注意两点一是abs对int重载没问题二是头文件里cstdlib或cmath提供了整数版本的absLeetCode环境默认包含直接写不会报错。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 只有一个点的时候答案是 0n 1当points只有一个元素时没有任何移动需要发生答案是0。我们的代码里循环从i 1开始len(points)为1时循环自然不执行ans就是0逻辑正确不用特判。但有些人会写“从第0个点开始依次到每个点最后再回到第0个点”这会多算一大段。记住访问所有点不等于闭合成环。终点就是最后一个点不需要回来。4.3 负坐标与 int 溢出看似安全的边界坐标范围是-10^4到10^4两个坐标相减的差的绝对值最大是2*10^4求和后最多约2*10^6int肯定够。但我还是建议在正式代码里用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只吃float64int要自己写。这不算算法坑但确实会浪费时间。尤其是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。n100时精确求解只能上状态压缩DP复杂度O(n²·2^n)n20已经到千万级别n100基本是天文数字。实际比赛里遇到这种题要么n很小比如15以内要么只能求近似解。所以LeetCode把这题的顺序定死其实是把NP难问题降级成了线性问题。“顺序固定”这个条件远比看起来更重要。5.2 只能上下左右移动变成曼哈顿距离求和如果题目去掉“对角线”只允许水平或垂直移动那相邻点之间就变成曼哈顿距离dx dy总耗时是sum(|x[i] - x[i-1]| |y[i] - y[i-1]|)拿示例[[0,0],[3,4]]对比就很明显允许对角线4秒。只允许横竖347秒。很多网格题都是曼哈顿距离模型比如计算城市街区里两栋楼之间的步行距离。什么时候用曼哈顿什么时候用切比雪夫记住一句话看移动方向个数四个方向是曼哈顿八个方向是切比雪夫。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)或者要求“必须经过某些额外点”那就又不一样了。把一个题目当成一颗种子在脑子里长出几个变种是性价比很高的练习方式。我现在的习惯是每做完一道简单题都强迫自己想一想“改了哪个条件就会变难”“这个模型还能用在哪”。这种方法比死磕难题有用得多毕竟面试时你永远不知道出题人会往哪个方向挖。