LeetCode 1266 这道题我印象挺深。不是因为难而是因为它非常典型地反映了一个容易被忽略的问题移动规则不同“距离”的定义就完全不同。题目给出若干个二维坐标点要求按顺序访问每一个点每秒可以向上、下、左、右或者斜对角走一格问最少需要多少秒。很多人第一反应是算欧几里得距离提交之后才发现自己理解偏了。这道题在 LeetCode 里叫 Minimum Time Visiting All Points也就是访问所有点的最小时间属于贪心与几何的入门题。它适合刚刷力扣的新手用来建立“移动规则与数学模型”之间对应的感觉也适合准备面试的同学用作距离度量的快速热身。1. 题面拆解它到底在考什么1.1 先看懂移动规则题目描述是在一个二维平面上给定 n 个整数坐标点 points[i] [xi, yi]要求按照数组给出的顺序访问所有点返回访问所需的最小秒数。关键限制是“每秒钟你可以垂直移动一格、水平移动一格或者斜对角移动一格”。也就是说你手里那个点永远落在整数网格上一次只能沿八个方向之一移动。我第一次做的时候差点把“斜对角移动”理解成任意方向的直线移动。后来在纸上画了一下才明白这道题的斜对角移动并不是从 (0,0) 到 (1,0.5) 这种直线而是从 (x, y) 直接跳到 (x1, y1) 这样的格子对角线。说白了移动能力和国际象棋里的王完全一样横、竖、两条 45 度对角线八个方向都能走。这个区别非常重要。假设从 (0,0) 要到 (4,2)。如果只能横竖走最少需要 426 秒如果能任意方向直线飞大概需要 4.47 秒但在八方向规则下你可以先斜着走两步到 (2,2)剩下两格水平走到 (4,2)总共 4 秒。这个 4 秒正好等于 max(4,2)。这个例子基本就是后面所有代码的依据。1.2 三种距离的一次对比这里其实涉及三个常见的距离概念。曼哈顿距离是 |dx| |dy|对应只能上下左右移动的街区式路径欧几里得距离是 sqrt(dx² dy²)对应可以在平面上任意方向直线移动而这题的八方向移动对应的叫切比雪夫距离公式是 max(|dx|, |dy|)。我把它们放在一起比较过用一个小表格可以看得很清楚距离类型公式对应移动规则(0,0)到(3,3)曼哈顿距离|dx| |dy|只能上下左右6欧几里得距离sqrt(dx² dy²)任意方向直线约4.24切比雪夫距离max(|dx|, |dy|)上下左右 对角线3从 (0,0) 到 (3,3)在八方向规则下走对角线三步就到了所以是 3 而不是 4.24。从 (0,0) 到 (5,2)先斜着走两步到 (2,2)再水平走三步到 (5,2)一共 5 秒正好是 max(5,2)。所以这道题表面上是模拟移动实际上考点只有一个你能不能把“八方向移动”快速翻译成 max(abs(dx), abs(dy))。翻译对了整个代码就是一个循环累加没有任何别的弯弯绕。1.3 这种距离模型有什么用可能有朋友觉得这只是棋盘上的玩具问题。其实切比雪夫距离在不少真实场景里都有对应物。比如一些规划得比较规整的城市街区行人既沿着横竖道路走也可以穿过街心广场或斜向步行道这时候计算两点之间的最短时间就接近这个模型。又比如游戏里的寻路如果允许角色在网格上走八方向移动的消耗通常就按切比雪夫距离来算。还有无人机或者机器人在栅格地图中的协同移动很多算法也直接用这类距离做初筛。出题人选这种规则一方面是因为它比纯横竖移动更接近真实世界的一部分场景另一方面是因为它能让题目有一个“反直觉”的点很多人的第一反应是 sqrt但实际答案是 max。这种“规则翻译”能力比代码能力本身更值得练习。2. 贪心思路与数学证明2.1 为什么答案是切比雪夫距离从一个点 p 移动到另一个点 q设 dx x2 - x1dy y2 - y1然后取绝对值得到 a |dx|b |dy|。在八方向移动规则下每一步可以让横坐标的变化量最多为 1纵坐标的变化量最多也为 1。如果横纵坐标都需要变化走对角线可以让两个坐标同时变化 1这是唯一的“一石二鸟”的移动方式。所以最优策略非常好描述先让较小那个差值通过斜行消掉再用剩余的水平或垂直步数补齐较大的差值。耗时就是先走 min(a, b) 步对角线再走 |a - b| 步直线总步数等于 max(a, b)。这个结论还可以从下界角度证明既然每一步最多只能让横坐标改变 1那么要完成 a 的横向差距至少需要 a 步同样要完成 b 的纵向差距至少需要 b 步。全程所需步数必须同时满足这两个下界所以至少是 max(a, b)。而前面说的“斜着走 min(a, b) 步再横着或竖着走 |a - b| 步”正好可以达到这个下界。下界可达自然就是最优。以后遇到贪心题可以多尝试“猜答案证下界构造方案”这个套路很多题的证明核心都在这里。2.2 为什么可以逐段相加题目里的点是有顺序的必须按 points 数组给定的顺序访问。从第 i 个点到第 i1 个点的最短时间是它们的切比雪夫距离从第 i1 个点到第 i2 个点又是一个独立的子问题。有人可能会问能不能在前一段绕一下路让后一段更快答案是不行。因为每个点的坐标是固定的你无论怎么绕最终到达第 i1 个点时坐标仍然是这个点本身不会因为绕路而变成“更靠近下一点”的位置。除非你故意不访问它但那不符合题目要求。所以整体最少时间就是每一段相邻点对最短移动时间之和。严谨一点说任何合法方案在访问第 i1 个点时都必须经过该点从该点出发到下一个点的时间不可能少于这两个点的切比雪夫距离。所以整体耗时是所有相邻点对距离的下界之和而逐段采用最优路径可以达到这个下界。一个问题只要限定“必须按给定顺序访问”往往都可以拆成相邻点对的叠加1266 是其中最直白的一道。2.3 复杂度与大数组表现实现上只需要一次遍历时间复杂度 O(n)额外空间 O(1)。这道题的原始约束里 n 很小就算写成 O(n²) 也不会超时但在面试里还是应该给出线性版本。如果以后遇到类似的题但点的数量扩大到 10^5 甚至 10^6线性遍历依然是最干净的做法。另外题目条件里的 “in the order given” 是很容易看漏的限定词。如果改成“可以任意重排访问顺序”问题性质就变了那可能涉及排序贪心、最小生成树甚至旅行商近似难度会完全不同。所以刷题时一定要先在题干里画出“顺序”这个词它往往决定了整个算法的方向。3. 代码实现与细节打磨3.1 三种语言的参考写法Python 版本from typing import List class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: total 0 for i in range(len(points) - 1): x1, y1 points[i] x2, y2 points[i 1] total max(abs(x1 - x2), abs(y1 - y2)) return totalJavaScript 版本var minTimeToVisitAllPoints function(points) { let ans 0; for (let i 0; i points.length - 1; i) { const [x1, y1] points[i]; const [x2, y2] points[i 1]; ans Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2)); } return ans; };C 版本class Solution { public: int minTimeToVisitAllPoints(vectorvectorint points) { int ans 0; for (int i 0; i 1 points.size(); i) { ans max(abs(points[i][0] - points[i 1][0]), abs(points[i][1] - points[i 1][1])); } return ans; } };三份代码的核心逻辑完全一致区别只在语法细节。Python 的列表解包写起来最干净x1, y1 points[i]这种赋值在看代码时非常直观JavaScript 也支持解构面试白板写起来很顺手C 则是直接按下标取坐标没有多余包装。只要理解了公式语言差异最多影响一两分钟打字时间。3.2 代码细节不是小事下面这些点是我实际提交或者帮别人 review 代码时经常提到的循环边界是头号问题。Python 写range(len(points) - 1)JavaScript 写i points.length - 1C 写i 1 points.size()。千万不要漏掉-1否则访问points[len]会造成越界。C 的越界是未定义行为本地运行可能碰巧没报错提交到评测机上就可能莫名其妙出错。用abs而不是自己写条件判断。有的同学喜欢写if (x1 x2) ... else ...虽然也能得到差值但abs加max更不容易漏情况。Python 的abs、JavaScript 的Math.abs、C 的std::abs都支持 int 类型直接用就好。累加变量的类型。这道题的坐标范围是 [-1000, 1000]int完全够用。但如果题目改编成坐标范围很大比如到 10^9那两点之差的绝对值可能到 2*10^9某些语言里继续用 int 就有溢出风险工程代码里建议直接用 long long。单点输入不需要特判。题目保证至少有一个点单个点的时候循环根本不执行函数自然返回 0。不过我在本地测试时仍然会主动试一次[[0,0]]防止自己写出访问points[1]这类错误。不要排序。题目限定按数组顺序访问代码里不要去sort(points)。一旦排序部分样例可能会碰巧通过但整体结果就是错的而且这种错误比较隐蔽不好查。3.3 一行流写法如果只是刷题图一乐Python 可以写成一行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(len(points) - 1))一行流利用了生成器表达式和sum的组合读起来很紧凑。我不建议在面试里第一版就这么写因为解释成本高而且容易在括号匹配上分心。更好的做法是先在白板上写清晰的多行版本确认思路后如果想展示 Python 功底再提一句“其实这个逻辑可以压缩成一行”。平时我自己也是先写清晰版确认通过后再顺手存一个精简版。4. 常见问题与排查实录4.1 我看过的典型错解第一类错解是算欧几里得距离。很多人看到平面坐标下意识就sqrt((x1-x2)^2 (y1-y2)^2)但题目根本不支持任意角度直线移动示例一跑就错。第二类错解是算曼哈顿距离。觉得斜着走也就是“先横再竖”把两步合并成一步确实省时间但缺少了“同时性”这个概念于是漏掉了max。第三类错解不是公式问题而是把点顺序打乱比如排序。这个错误对某些样例答案会和正确答案一样非常容易让人忽略。我还见过一种奇怪的写法把每段移动拆成“x 方向差加 y 方向差除以 2”之类从思路上就偏了。如果身边有朋友这样写我一般建议他先画一张从 (0,0) 到 (5,2) 的格子图自己走一遍再回头看看公式基本一下就能理解。4.2 本地测试应该覆盖哪些样例我自己调试几何题时会在本地跑一组小样例而不是直接盲提交。下面这组覆盖了大部分边界情况[[0,0],[1,1]]期望 1验证对角线单步。[[0,0],[1,0]]期望 1验证纯水平。[[0,0],[0,1]]期望 1验证纯垂直。[[0,0],[5,2]]期望 5验证“斜加横”的组合路径。[[0,0]]期望 0验证单点。[[0,0],[0,0]]期望 0验证相同点。把这些样例跑一遍再提交基本一次过。如果发现某个样例结果不对我会在循环里临时打印出 dx、dy 和 max 的值逐段检查累加过程而不是盯着总答案发呆。调试几何题最好的工具就是 print说白了就是一个一个点对着看。4.3 排错心法遇到答案错误先确认公式公式没问题再看循环边界最后检查是不是误用排序或欧几里得距离。这道题不存在超时问题所以不需要去优化复杂度和引入额外数据结构复杂度优化带来的新增 bug 在这里完全可以避开。如果是在 C 里出现编译错误多半是abs的头文件问题。std::abs对 int 的重载定义在cstdlib里很多编辑器会隐式引入但规范起见还是建议显式包含头文件。另外一些在线评测平台对 C 版本要求不同如果abs报重载歧义可以改成std::abs或者直接手写int dx x1 x2 ? x1 - x2 : x2 - x1;来绕开但这样写不如abs直观。5. 延伸距离模型与面试扩展5.1 距离模型的选择是真正的考点LeetCode 1266 的核心不在写代码而在选对数学模型。面试官如果考这道题通常想确认你对坐标、移动规则和距离度量的敏感度。很多人被复杂题训练成“先想 DP、二分、图搜索”遇到简单题反而容易掉以轻心。所以我在面试时会先口头复述一遍每秒可以沿八个方向之一移动因此两点间时间是 max(|dx|, |dy|)。这一步说清楚后面代码就是顺水推舟。如果移动规则改成只能上下左右那就是曼哈顿距离改成任意角度直线才是欧几里得距离。很多资料会把“棋盘格子里国王的走法”和“切比雪夫距离”绑在一起讲其实就是同一个模型。这类题在 LeetCode 热门 100 题里不一定排得上号但它经常作为更复杂题目的前置组件出现比如一些 BFS、贪心、棋盘路径题里会突然冒出一段切比雪夫距离的计算。5.2 与二分题的距离感对比LeetCode 073 爱吃香蕉的狒狒是另一个方向的题它考察的是二分答案给你一个速度区间去验证能否在 H 小时内吃完。它和 1266 没有公式上的关系但把两者放在一起看能体会出“识别题型”的重要性。1266 是几何加贪心看到八方向移动就想到切比雪夫距离073 是二分看到“最小速度”“上限区间”就想到枚举答案再验证。刷题到一定量级之后最快的进步方式不是背代码而是建立“题目条件到算法方向”的映射。如果你想参加周赛比如准备类似周赛 430 那样节奏的比赛1266 这种题很适合当热身。它提醒你周赛里的简单题往往拼的不是算法复杂度而是谁能在最短时间里读对规则。能把简单题又快又准地吃掉后面几道题才有更多时间抠细节。5.3 如果面试官追问追问一如果点数量增加到 10^6你的解法还能跑吗可以O(n) 遍历加 O(1) 额外空间常量开销很小基本不受数据量影响。追问二如果允许任意顺序访问所有点求最小总时间你会怎么做这就是另一个问题了距离矩阵加旅行商思想n 大时只能找近似解或者看具体约束。回答时不需要展开太多但要能意识到“顺序限定”是关键区别。追问三如果移动规则改成“每秒移动不超过一个单位长度方向任意”答案会变成欧几里得距离之和吗这时候要考虑取整问题以及点是否必须停留在整数坐标上。能说出“取决于点是否必须是整数格子点”就已经体现出了思维的严密性。5.4 几个值得练的扩展方向第一个方向是与曼哈顿距离相关的经典套路比如把切比雪夫距离转换成曼哈顿距离的坐标变换令 u x yv x - y很多距离题转换之后会变得很好算。第二个方向是 BFS 里的八方向移动很多棋盘最短步数题都用同一套方向数组1266 的移动规则正好是它的简化版。第三个方向是把这类距离用在聚类或者异常检测的题里虽然那已经不是 LeetCode 简单题的范围但理解距离度量之间的换算对阅读一些论文或开源代码也有帮助。想提升的话可以按“距离度量”这个关键词去题单里搜连续做几道类似题就会形成题感。记住一个公式很容易难的是在读完题目的一瞬间就意识到该用哪个公式。最后说点我个人的体会。第一次做完 1266收获最大的不是背住 max(abs(dx), abs(dy))而是学会在读题时先圈出“移动规则”四个字。很多题的坑不在算法在于题目用一句话把数学模型定死了你没读出来后面全是白算。我自己在画 (0,0) 到 (5,2) 的路径时也对比过曼哈顿路径和切比雪夫路径的差别那次对比之后这类题基本就没再错过。再分享一个小习惯凡是几何或棋盘题写代码前先画一个 5x5 的小网格把样例拿手走一遍。这个习惯看着土但真能帮你避免因为距离模型选错而导致的返工。LeetCode 1266 不难但它是值得反复咀嚼的一道入门题。