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