1. 先看題目一個被低估的“送分題”LeetCode 1266題目名很直白訪問所有點的最小時間。給定平面上 n 個點按數(shù)組給出的順序依次訪問從第一個點出發(fā)每秒鐘可以沿水平、豎直或者對角線方向移動一格問最少需要多少秒走完全程。先別急著覺得“這不就是模擬嗎”這個題最大的坑在于移動規(guī)則。很多第一次刷到的朋友會下意識套用“歐幾里得距離”或者“曼哈頓距離”的思路結(jié)果發(fā)現(xiàn)樣例都對不上或者自己推導(dǎo)出來的公式和答案差了一點。原因很簡單題目允許斜向移動而且是“每秒鐘可以沿水平、豎直或?qū)蔷€方向移動一格”。這一個條件直接改變了距離的定義。這道題在 LeetCode 上被標記為“簡單”但我個人覺得它更適合作為“貪心思維的入門熱身題”。它不涉及復(fù)雜的數(shù)據(jù)結(jié)構(gòu)不需要動態(tài)規(guī)劃也沒有抽象的排序策略核心就是一個樸素的觀察從點 A 走到點 B斜著走永遠比繞直角走更省時間所以每一步的最優(yōu)決策都是獨立的局部最優(yōu)就是全局最優(yōu)。這不正是貪心算法最原始、最干凈的樣子嗎這篇文章適合三類人看一是剛刷完數(shù)組、字符串、鏈表想開始接觸貪心算法但被“區(qū)間調(diào)度”“跳躍游戲”嚇得不敢動的新手二是面試前想快速過一遍“簡單題”里藏著的數(shù)學(xué)原理的老手三是平時寫代碼習(xí)慣了 for 循環(huán)嵌套想看看“一行版”到底是怎么壓縮出來的朋友。先說結(jié)論相鄰兩點之間的最短時間等于兩點橫坐標之差的絕對值和縱坐標之差的絕對值中的較大者也就是max(|x1 - x2|, |y1 - y2|)。把所有相鄰點的這個值加起來就是答案。這個結(jié)論看起來簡單到像一個腦筋急轉(zhuǎn)彎但它背后藏著“為什么斜著走能同步縮短兩個方向的距離”這個核心問題。下面我一步步把這個結(jié)論從直覺到數(shù)學(xué)到代碼全部掰開講清楚。2. 移動規(guī)則決定的不是“路程”而是“距離公式”2.1 三種距離歐式、曼哈頓、切比雪夫要真正理解這道題必須先搞清楚一個底層概念平面上兩點之間的距離不是唯一的。我們初中幾何學(xué)的兩點的距離是歐幾里得距離也就是直線距離公式是sqrt(dx2 dy2)。但在實際場景里距離的定義取決于你“怎么走”。舉個很直觀的例子你在一個方格城市里街道都是橫平豎直的從 A 到 B 不能穿樓只能沿著街道走。這時候你走的距離就不是直線距離而是橫向要走的格子數(shù)加上縱向要走的格子數(shù)|dx| |dy|這個叫曼哈頓距離。名字來源于紐約曼哈頓的街區(qū)布局。但在 LeetCode 1266 里移動規(guī)則變成了“可以斜著走”而且是同時向水平和對角線方向移動每移動一格都算 1 秒。這其實就是第三種距離——“切比雪夫距離”公式是max(|dx|, |dy|)。為什么叫切比雪夫距離因為在國際象棋里國王King每次只能走一格但可以向周圍 8 個方向任意移動。國王從棋盤一格走到另一格需要的最少步數(shù)恰好就是max(|dx|, |dy|)。這道題里的移動方式和國際象棋國王一模一樣。2.2 為什么斜著走能“同時”縮短兩個方向這是整道題的核心直覺也是最容易講不清的地方。假設(shè)從(0, 0)出發(fā)要去(5, 3)。如果你只能水平向右、豎直向上走曼哈頓規(guī)則那你需要先走 5 步到(5, 0)再走 3 步到(5, 3)一共 8 步。但如果你允許斜著走斜著走一步的同時既向右了一格又向上一格。你先斜著走 3 步到達(3, 3)——注意此刻橫向需求還剩 2縱向需求已經(jīng)清零。接下來再水平向右走 2 步到達(5, 3)。總步數(shù) 3 2 5。這 5 步恰好就是max(5, 3) 5。你發(fā)現(xiàn)規(guī)律沒有斜著走是用來“消掉”橫縱距離中較小的那一部分。兩個方向的距離差多少斜著走能覆蓋多少最后剩下的那個差值就是你必須直著走的距離。所以總步數(shù)永遠是“兩個距離中的較大者”——因為較小的那部分被斜著走“順路”解決了。這個直覺一旦建立整個題目就豁然開朗了。2.3 一個反直覺的驗證不是加和是取大為了讓你徹底信服再看兩組極端數(shù)據(jù)。第一組(0, 0)到(100, 100)。如果按曼哈頓距離算要 200 秒按切比雪夫距離算只要 100 秒。實際情況也是 100 秒——你一直斜著走就完了每一步都同時橫縱各進一格100 步之后剛好到達。兩個方向的需求永遠相等所以一條對角線走到黑。第二組(0, 0)到(100, 0)。橫向距離 100縱向距離 0取大結(jié)果是 100 秒。這個很好理解縱向沒有需求你只需要水平走 100 格。但注意就算你中途偶爾斜著走再走回來也不會更優(yōu)因為斜著走會產(chǎn)生“多余的縱向位移”最后還要花額外的步數(shù)修正。所以兩點間可達的最小時間就是兩個方向絕對差的最大值。它既不是dx dy也不是sqrt(dx2 dy2)而是max(|dx|, |dy|)。一句話總結(jié)在八個方向的移動模型下時間被“短板”限制但決定速度的是“長板”。3. 為什么能“貪”相鄰點獨立最優(yōu)3.1 題目順序是固定的但它仍然是一個貪心問題有一個常見的疑問題目給的點的順序是固定的我必須從points[0]到points[1]再從points[1]到points[2]……既然順序都定死了還有什么貪心不貪心這是一個好問題。很多人理解的貪心是“從一堆選項里挑最優(yōu)”而這道題看起來沒有任何選擇。但實際上即使路線必須按順序走每一步的移動方式仍然存在選擇空間。比如從(0, 0)到(5, 3)你可以先斜走 3 步再橫走 2 步也可以先橫走 1 步再斜走 3 步再橫走 1 步甚至可以先豎著多走幾步繞個路。這些不同的移動策略耗時完全不同。貪心在這里表現(xiàn)為每一段路程都選擇耗時最少的移動方式不回頭、不繞路、不“為后續(xù)省力”而犧牲當前步。而為什么這種局部最優(yōu)能成立因為段與段之間完全獨立——你在points[i]到points[i1]怎么移動不會影響你到達points[i1]時的位置和狀態(tài)。到達點是確定的所以上一段的結(jié)束狀態(tài)就是下一段的起始狀態(tài)不存在“先多走一段路能讓我接下來更快”的可能性。這和經(jīng)典的貪心問題——比如“用最少的硬幣湊出金額”——有本質(zhì)區(qū)別。硬幣問題里你如果先用大面額硬幣可能影響后續(xù)能否湊整。但 1266 里不存在這種耦合。每段路程只有起點和終點這兩個約束中間怎么走完全自由所以每段取最優(yōu)總和必然最優(yōu)。3.2 如果題目允許“自由選擇訪問順序”這里做個延伸思考這也是面試官很喜歡追問的變體如果題目改成“可以以任意順序訪問所有點求最短時間”那還能不能貪心答案是不能了。因為這時候問題變成“給定一組點求一條經(jīng)過所有點的最短路徑”本質(zhì)上是一個旅行商問題TSP的變體。在二維平面上雖然有些啟發(fā)式算法但不存在多項式時間的精確解復(fù)雜度隨點數(shù)指數(shù)增長。這個變體和原題的差距就像“按順序走完一條街”和“在市區(qū)里規(guī)劃一條最短路線把所有快遞送完”的差距。前者是數(shù)學(xué)題后者是運籌學(xué)難題。3.3 貪心的邊界局部最優(yōu)與全局最優(yōu)的一致性驗證我們還可以用一個更嚴謹?shù)姆绞絹眚炞C“每段最優(yōu)帶來全局最優(yōu)”的正確性。設(shè)總時間T等于所有相鄰點距離之和T sum(d(points[i], points[i1]))其中d是我們定義的切比雪夫距離。因為每段d都是該段的最小值任何其他移動策略都會讓該段時間 d?？倳r間是各段時間之和每一項都至少是d所以任何策略的總時間至少是sum(d)。而我們構(gòu)造一個策略剛好達到這個下界——每段都按切比雪夫距離的最短方式走——所以這個下界就是最小值。這就是貪心算法里最標準也最令人舒服的證明結(jié)構(gòu)先證明一個下界再構(gòu)造達到下界的方案。一旦兩步都成立你就知道答案不可能更小了。這個證明過程我覺得比題目本身更重要因為很多貪心題的正確性證明套路都是這樣。4. 代碼實現(xiàn)從暴力模擬到 Python 一行版4.1 基礎(chǔ)實現(xiàn)雙層循環(huán)求和先寫出最容易理解的版本也方便驗證公式的正確性class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: ans 0 for i in range(len(points) - 1): x1, y1 points[i] x2, y2 points[i 1] ans max(abs(x1 - x2), abs(y1 - y2)) return ans這段代碼的邏輯非常簡單遍歷相鄰點對計算橫縱坐標差的絕對值取較大值累加。時間復(fù)雜度O(n)空間復(fù)雜度O(1)。你可能覺得這段代碼太簡單沒有任何技巧。但恰恰是這種樸素實現(xiàn)最能體現(xiàn)對題目的理解程度。面試的時候先寫出這種清晰版本再提優(yōu)化或一行版觀感遠好于一上來就寫一行表達式。4.2 一行版的拆解過程一行版的核心是 Python 的zip和生成器表達式配合sumclass Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: return sum(max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1])) for p1, p2 in zip(points, points[1:]))一行版做了三件事zip(points, points[1:])把點列表和它去掉第一個元素后的列表打包得到(points[0], points[1])、(points[1], points[2])……這一下子就完成了“相鄰點對”的配對不需要像基礎(chǔ)版那樣用索引i和i 1去訪問。生成器表達式for p1, p2 in zip(...)逐個點對計算max(abs(p1[0] - p2[0]), abs(p1[1] - p2[1]))等價于基礎(chǔ)版循環(huán)體里的表達式。sum(...)把所有點對的結(jié)果累加。這三個機制配合起來就把顯式的ans 循環(huán)壓縮成了函數(shù)式的一行。本質(zhì)上做的事情和基礎(chǔ)版完全一樣只是語法層面的壓縮。4.3 再進一步用zip解包的寫法如果你想展示對解包語法的熟練度還可以這樣寫class Solution: def minTimeToVisitAllPoints(self, points: List[List[int]]) - int: return sum(max(abs(a - c), abs(b - d)) for (a, b), (c, d) in zip(points, points[1:]))這里(a, b)和(c, d)直接解包了前后兩個點的橫縱坐標表達式里就不需要再寫p1[0]這種索引訪問了。從可讀性角度這種寫法比p1[0] - p2[0]更清晰也更能體現(xiàn) Python 解包語法的優(yōu)雅。不過我得提醒一句一行版在 LeetCode 上能跑在實際工程項目里不建議這么寫。zip(points, points[1:])會額外創(chuàng)建一個points[1:]的副本雖然只持有引用但仍然是 O(n) 的額外空間而且一行表達式對調(diào)試不友好。但作為刷題展示或者作為理解 Python 函數(shù)式編程的練習(xí)它確實很漂亮。4.4 三種代碼的對比小結(jié)版本可讀性空間復(fù)雜度適用場景基礎(chǔ)版顯式循環(huán)最高O(1)面試講解、工程代碼、教學(xué)一行版zip sum中等O(n)points[1:]副本刷題炫技、理解函數(shù)式寫法解包一行版中等偏上O(n)想要兼顧優(yōu)雅與可讀性時如果你想兼顧效率和可讀性又不想要points[1:]的副本可以用索引表達式return sum(max(abs(points[i][0] - points[i1][0]), abs(points[i][1] - points[i1][1])) for i in range(len(points) - 1))這段既不創(chuàng)建切片副本又保持了一行表達式的緊湊感是工程中更穩(wěn)妥的折中方案。5. 邊界情況、雷區(qū)與性能陷阱5.1 只有一個點或空數(shù)組按題目約束points的長度至少為 1。如果長度是 1循環(huán)體一次都不執(zhí)行返回 0。這個邏輯基礎(chǔ)版和一行版都天然成立不需要額外寫if判斷。但如果你在代碼審查時看到有人加了if len(points) 1: return 0也不要覺得多余——它不影響正確性只是防御式編程的習(xí)慣。在面試里主動提一句“這個邊界條件被循環(huán)結(jié)構(gòu)天然覆蓋”能體現(xiàn)你對邊界的敏感度。5.2 坐標可為負題目沒有限制坐標必須為正。比如(-7, -3)到(5, 2)計算abs(-7 - 5) 12abs(-3 - 2) 5結(jié)果是 12。絕對值的存在讓負數(shù)坐標不影響正確性。這里唯一的風(fēng)險是初學(xué)者可能會下意識用max(x1, x2) - min(x1, x2)來代替abs(x1 - x2)兩種寫法都正確但abs更清晰、更不容易出錯。5.3 大坐標與溢出Python 的整數(shù)是任意精度的所以即使坐標到10^9級別也不會溢出。但如果你是 C 或 Java 選手int可能不夠用取決于題目給的約束范圍需要用long long。這屬于語言層面的差異Python 選手不需要擔(dān)心。5.4 常見錯誤誤用曼哈頓距離這個錯誤出現(xiàn)的頻率高到我單獨拿出來說。很多人第一眼看到“水平、豎直、對角線都可以走”會覺得“那肯定比曼哈頓快”但寫代碼時還是手滑寫成了abs(dx) abs(dy)。這會導(dǎo)致答案偏大。比如兩點為(1, 1)到(4, 5)曼哈頓距離是3 4 7切比雪夫距離是max(3, 4) 4。一個點對就差 3 秒點多了差異就非常明顯。怎么避免這個錯誤每次寫完之后用最簡單的用例自測points [[0, 0], [1, 1]]答案應(yīng)該是 1斜著一步就到而不是 2。如果寫成dx dy得到 2立刻就能發(fā)現(xiàn)。5.5 復(fù)雜度與 LeetCode 性能的“錯覺”這個題的O(n)復(fù)雜度在 LeetCode 上跑起來大約是幾十毫秒級別。就算點數(shù)到10^5也只要求一次遍歷完全沒有性能壓力。但如果你用了points[1:]的一行版雖然是 O(n) 的時間和 O(n) 的空間實測也不會超時。這就是 LeetCode “簡單題”的典型特征——即使你寫出了次優(yōu)版本測試數(shù)據(jù)量也遠構(gòu)不成威脅。但我要強調(diào)不要把“沒超時”當成“算法最優(yōu)”的理由。在面試場景中面試官看到一行版通常會追問空間復(fù)雜度這時候如果你能準確說出它比基礎(chǔ)版多用了 O(n) 的切片空間并說明在什么場景下這個額外空間不可接受這反而是一個加分項。5.6 關(guān)于“貪心證明”的追問我遇到過不止一次面試官在候選人寫完代碼后追問“你憑什么說每段取最短時間總時間就一定最短萬一后面某一段因為前面的走法而變長呢”正確回答的姿勢是因為后一段的起點是固定的所以前一段的走法不會改變后一段的起點和終點也就不會影響后一段的最小時間。每一段是獨立的決策沒有耦合局部最優(yōu)自然疊加成全局最優(yōu)。如果面試官再深挖你可以補充如果我們把每個點對的切比雪夫距離定義為一個函數(shù)d(p, q)這個函數(shù)滿足三角不等式嗎答案是不一定滿足固定版本下的“繞路反而更短”不存在因為d已經(jīng)是兩點之間的最短路徑長度。三角不等式在這里體現(xiàn)為d(a, c) d(a, b) d(b, c)——但那是另一個問題的分析工具在這個按順序訪問的設(shè)定下用不上。6. 從 1266 看開去一道簡單題背后的三個通用能力6.1 識別“距離定義”的能力很多算法題的成績差距不在于你會不會寫代碼而在于你能不能識別出題人在用哪種“距離模型”。LeetCode 1266 考的是切比雪夫距離換一個背景它可以變成“機器人網(wǎng)格尋路最短步數(shù)”曼哈頓距離再換一個背景可以是“二維坐標下救援船的最短時間”切比雪夫距離。我自己的一個習(xí)慣是拿到一題第一件事不是打開編輯器而是先問自己三個問題這個移動規(guī)則對應(yīng)哪種距離公式點和點之間有沒有耦合順序是固定的還是自由選擇的這三個問題回答完解法往往已經(jīng)浮出水面了。6.2 數(shù)學(xué)推導(dǎo)的最小閉環(huán)定義 → 歸納 → 邊界這一題里我們實際上做了三步完整的數(shù)學(xué)推導(dǎo)定義兩點間的移動模型等價于切比雪夫距離max(|dx|, |dy|)歸納通過“斜著走能同步縮短兩個方向”的直覺驗證了取大而不是取和的合理性邊界空數(shù)組、單點、負數(shù)坐標、大數(shù)都在公式和代碼中被自然覆蓋。這個“最小閉環(huán)”值得刻在腦子里。很多刷題的人看到一個題直接開始寫代碼結(jié)果代碼邏輯在常見用例上沒問題一到邊界就崩。原因就是沒有先做數(shù)學(xué)層面的“邊界掃描”。6.3 “暴力枚舉 推導(dǎo)公式 數(shù)學(xué)構(gòu)造”的思維鏈路題目相關(guān)的熱搜詞里出現(xiàn)了“暴力枚舉推導(dǎo)公式數(shù)學(xué)構(gòu)造”這其實概括了一個更通用的解題套路非常適合用來復(fù)盤 1266暴力枚舉如果我不知道切比雪夫距離公式我可以直接 BFS 模擬從一點到另一點的最短步數(shù)點對少時也能跑出答案。但 BFS 對每個點對都要做一遍復(fù)雜度是O(n * max_coord)點數(shù)一多就廢了推導(dǎo)公式通過觀察移動規(guī)則推導(dǎo)出max(|dx|, |dy|)直接 O(1) 計算每個點對數(shù)學(xué)構(gòu)造上面的推導(dǎo)本質(zhì)上是一個構(gòu)造性證明——我們不僅知道答案是max還知道怎么走能走到先斜后直這保證了公式的現(xiàn)實可執(zhí)行性。這三步對應(yīng)了三種思維層次暴力求解保證正確性公式推導(dǎo)保證高效性構(gòu)造證明保證可復(fù)現(xiàn)性。我覺得這一題的真正的價值不在于“你這么簡單還分析這么久”而在于它把這三步壓縮到了最小規(guī)模非常適合用來練習(xí)思維鏈路。6.4 后續(xù)擴展如果題目變成“曼哈頓規(guī)則”或“歐式規(guī)則”最后留一個思考題給你自己驗證如果把移動規(guī)則改成只能上下左右走曼哈頓距離答案就變成每段|dx| |dy|的總和。如果再改成可以沿任意方向走任意距離但每單位距離耗時 1答案就變成每段歐幾里得距離sqrt(dx2 dy2)的總和而且這種模式下“斜向直接走直線”就是唯一最優(yōu)解沒有任何貪心選擇的余地。三種移動模型三種距離公式同一道題三種答案。理解了這個1266 就算真正吃透了。