這一篇是貪心算法專(zhuān)題的第六篇也是整個(gè)系列的收官。前五篇我們磨了基礎(chǔ)模板刷了經(jīng)典例題也踩了不少證明上的坑。但說(shuō)實(shí)話(huà)模板背得再熟碰到新題還是會(huì)慌因?yàn)樨澬念}最難的不是代碼而是“怎么想到這個(gè)貪心策略”。今天這篇我想跳出題目本身把藏在貪心算法背后的兩種思維聊透一件叫降維打擊一件叫錯(cuò)位重構(gòu)。順手再用刪數(shù)問(wèn)題這條主線(xiàn)把兩件事串起來(lái)讓剛?cè)腴T(mén)的朋友也能看明白。先交代這篇適合誰(shuí)。如果你已經(jīng)在刷貪心題但總靠記憶同類(lèi)題來(lái)蒙策略或者經(jīng)常出現(xiàn)“貪心策略看起來(lái)沒(méi)問(wèn)題提交就是過(guò)不了”的窘境這篇會(huì)給你一套完整的思考框架。如果你剛學(xué)完貪心基礎(chǔ)也不用被“降維”“重構(gòu)”這些詞嚇到它們只是兩種具體的解題手段我會(huì)用非常直白的例子拆開(kāi)講。配合這個(gè)專(zhuān)題前五篇的內(nèi)容這一篇算是把所有貪心的思考方式收束到一個(gè)位置上。1. 貪心專(zhuān)題收官先聊聊我對(duì)貪心的整體理解1.1 貪心不是“拍腦袋”局部最優(yōu)與全局最優(yōu)的辯證關(guān)系很多人初學(xué)貪心時(shí)覺(jué)得貪心就是“每一步選當(dāng)前最好的”這話(huà)對(duì)但容易誤導(dǎo)。真正可用的貪心策略并不是先射箭后畫(huà)靶而是要先證明“每一步當(dāng)前最好”確實(shí)能通向“全局最好”。這一點(diǎn)我在專(zhuān)題第一篇就強(qiáng)調(diào)過(guò)今天收官再展開(kāi)講一遍每一步都做局部最優(yōu)選擇最終得到全局最優(yōu)解這件事需要兩個(gè)前提——貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)。貪心選擇性質(zhì)是說(shuō)局部最優(yōu)的選擇一定是某個(gè)全局最優(yōu)解的第一個(gè)選擇最優(yōu)子結(jié)構(gòu)是說(shuō)做出這個(gè)選擇后剩下的子問(wèn)題仍然可以用同樣的貪心策略繼續(xù)處理。兩個(gè)前提缺一個(gè)貪心就成了賭博。我習(xí)慣用一個(gè)下坡的例子幫助理解。假設(shè)你想從山頂走到山腳水庫(kù)如果每一步都選最陡的下坡方向在理想地形下確實(shí)能走到最低點(diǎn)。但現(xiàn)實(shí)地形常有山谷和埡口一直選最陡坡可能把你帶進(jìn)一個(gè)低洼處那里不是全局最低點(diǎn)。這個(gè)例子不嚴(yán)謹(jǐn)?shù)『谜f(shuō)明了“局部最優(yōu)不等于全局最優(yōu)”的直覺(jué)來(lái)源。做題時(shí)如果只靠直覺(jué)選策略很容易被樣例欺騙真正該做的是把“為什么局部最優(yōu)能帶出全局最優(yōu)”用反證法或交換論證寫(xiě)清楚。1.2 貪心算法的適用邊界什么題能貪什么題不能貪判斷一道題能不能用貪心最有效的方法是先找反例。我刷題多年最常踩的坑就是看到一個(gè)題就條件反射地排個(gè)序然后從頭掃到尾結(jié)果在某些邊界數(shù)據(jù)上翻車(chē)。舉個(gè)最經(jīng)典的例子0-1背包問(wèn)題不能貪心但分?jǐn)?shù)背包可以貪心。同樣是“每單位價(jià)值越高越好”的思路分?jǐn)?shù)背包允許拆開(kāi)物品所以局部?jī)r(jià)值最大可以無(wú)縫疊加成全局價(jià)值最大0-1背包不允許拆選了單位價(jià)值最高的物品后剩余空間可能裝不下任何高價(jià)值物品反而讓整體價(jià)值變低。這就是適用邊界的問(wèn)題。貪心題通常有個(gè)共同點(diǎn)決策之間不會(huì)“互相干擾”到無(wú)法修正的程度或者干擾可以被某種機(jī)制修正。一旦發(fā)現(xiàn)當(dāng)前選擇會(huì)永久性地破壞后面的可能性就要警惕這題是不是不能用貪心或者是否需要給貪心加上反悔機(jī)制。后面第三部分我們會(huì)專(zhuān)門(mén)講“錯(cuò)位重構(gòu)”其實(shí)就是在擴(kuò)展這個(gè)邊界——讓貪心策略允許出錯(cuò)然后通過(guò)堆等結(jié)構(gòu)把錯(cuò)誤修正回來(lái)。1.3 專(zhuān)題脈絡(luò)回顧從基礎(chǔ)模板到兩大進(jìn)階思維這個(gè)專(zhuān)題前五篇的內(nèi)容我簡(jiǎn)單梳理一下脈絡(luò)方便新讀者定位。第一篇是貪心基礎(chǔ)與證明方法講了貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)并引入了交換論證。第二篇集中講排序型貪心比如活動(dòng)安排、會(huì)議室、最少箭射氣球等區(qū)間類(lèi)問(wèn)題。第三篇講的是帶權(quán)調(diào)度和狀態(tài)貪心比如任務(wù)規(guī)劃、加油站問(wèn)題。第四篇引入堆輔助貪心重點(diǎn)講“當(dāng)前最值”如何參與決策。第五篇開(kāi)始涉及反悔貪心用一個(gè)動(dòng)態(tài)維護(hù)的堆來(lái)撤銷(xiāo)之前的決策。每一篇都有大量例題建議沒(méi)看過(guò)的讀者先補(bǔ)前面的內(nèi)容。今天這第六篇要做的是把前面所有思維收攏成兩個(gè)關(guān)鍵詞。降維打擊指的是把看似復(fù)雜的多維決策問(wèn)題化簡(jiǎn)成“排序掃描”的一維問(wèn)題錯(cuò)位重構(gòu)指的是當(dāng)貪心策略在局部做出了不夠優(yōu)的選擇時(shí)通過(guò)額外的數(shù)據(jù)結(jié)構(gòu)把這些選擇替換或撤銷(xiāo)從而把整體帶回全局最優(yōu)。接下來(lái)的每一部分我都會(huì)用具體題目來(lái)說(shuō)明而不是空談概念。特別是刪數(shù)問(wèn)題雖然題目本身不算難但它能同時(shí)把這兩個(gè)思維展示得淋漓盡致所以我想把它作為整個(gè)專(zhuān)題的收官例題。2. 降維打擊把復(fù)雜決策轉(zhuǎn)成排序與掃描2.1 降維打擊的核心把決策問(wèn)題翻譯成排序問(wèn)題先說(shuō)說(shuō)什么叫降維打擊。很多貪心題看起來(lái)要處理多個(gè)維度的信息比如每個(gè)任務(wù)有開(kāi)始時(shí)間、結(jié)束時(shí)間、權(quán)重、價(jià)值每個(gè)物品有重量、體積、價(jià)值選起來(lái)要同時(shí)考慮好幾個(gè)因素頭腦很容易亂。降維打擊的思路是找到其中一個(gè)最關(guān)鍵的量按它排序然后讓剩余維度的信息在一次線(xiàn)性?huà)呙柚凶匀槐惶幚淼?。排序就是把一個(gè)高維決策空間壓成一維的關(guān)鍵操作。為什么排序能起到這個(gè)作用因?yàn)榕判蚝蠛罄m(xù)掃描只需要維護(hù)“截止到目前為止的狀態(tài)”當(dāng)前要做的決策通常只和上一個(gè)狀態(tài)有關(guān)不需要回溯太多。以活動(dòng)安排為例有若干個(gè)活動(dòng)每個(gè)活動(dòng)有開(kāi)始時(shí)間和結(jié)束時(shí)間目標(biāo)是選擇盡可能多的互不重疊的活動(dòng)。如果同時(shí)想開(kāi)始時(shí)間和結(jié)束時(shí)間兩個(gè)維度決策模型是二維的但一旦把所有活動(dòng)按結(jié)束時(shí)間排序那么從早到晚依次掃描每次選擇當(dāng)前結(jié)束時(shí)間最早、且與已選活動(dòng)不沖突的活動(dòng)就能得到全局最多數(shù)量。這個(gè)結(jié)論的正確性可以用交換論證說(shuō)明在任意一個(gè)最優(yōu)解中如果把第一個(gè)活動(dòng)換成所有活動(dòng)中結(jié)束時(shí)間最早的那個(gè)肯定不會(huì)減少可選活動(dòng)的數(shù)量。因?yàn)樽钤缃Y(jié)束的活動(dòng)只會(huì)更早讓出時(shí)間不會(huì)讓后面的活動(dòng)失去機(jī)會(huì)。這就是“排序貪心選擇”的降維威力——把“選哪些”變成“在什么時(shí)刻選哪一個(gè)”。如果你做題時(shí)發(fā)現(xiàn)題目里多個(gè)量糾纏在一起第一反應(yīng)應(yīng)該是思考排序依據(jù)放在哪個(gè)量上能讓后面的一次掃描變得有決定性。2.2 區(qū)間類(lèi)問(wèn)題里的降維實(shí)例區(qū)間問(wèn)題是降維打擊最集中的戰(zhàn)場(chǎng)。除了活動(dòng)安排還有幾個(gè)非常經(jīng)典的變體無(wú)重疊區(qū)間、合并區(qū)間、最少的箭引爆氣球、會(huì)議室最多容納數(shù)量。這些題看起來(lái)解法各不相同但底層都是同一個(gè)動(dòng)作——按端點(diǎn)排序再線(xiàn)性?huà)呙?。無(wú)重疊區(qū)間這題要求移除盡可能少的區(qū)間使得剩下的區(qū)間互不重疊。如果正面思考“移除哪些”選擇空間很大但反過(guò)來(lái)想移除最少等價(jià)于保留最多這就直接轉(zhuǎn)化成了活動(dòng)安排問(wèn)題。按結(jié)束時(shí)間排序后貪心地保留每一個(gè)不與上一個(gè)保留區(qū)間沖突的區(qū)間就是最優(yōu)解。合并區(qū)間則是按左端點(diǎn)排序然后掃描時(shí)維護(hù)當(dāng)前合并區(qū)間的左右邊界遇到一個(gè)區(qū)間的左端點(diǎn)小于等于當(dāng)前右邊界就擴(kuò)展右邊界否則把當(dāng)前區(qū)間收尾、開(kāi)啟新區(qū)間。最少的箭引爆氣球這題我第一版做的時(shí)候也踩過(guò)坑。氣球是水平區(qū)間箭垂直射出一支箭能射穿所有與之相交的區(qū)間。剛看到題時(shí)我想按左端點(diǎn)排序結(jié)果在范例之外的數(shù)據(jù)上出錯(cuò)。后來(lái)意識(shí)到應(yīng)該按右端點(diǎn)排序每次從當(dāng)前區(qū)間的右端點(diǎn)射出這樣能保證這支箭穿過(guò)所有與它相交的后續(xù)區(qū)間數(shù)量一定是最少的。這個(gè)例子再次說(shuō)明降維的關(guān)鍵不只是“排序”而是“選擇哪個(gè)維度排序”。會(huì)議室問(wèn)題同時(shí)最多有多少個(gè)會(huì)議則換了一種降維方式把每個(gè)會(huì)議的開(kāi)始事件和結(jié)束事件拆成兩個(gè)獨(dú)立的時(shí)間點(diǎn)全部丟進(jìn)一個(gè)數(shù)組排序然后掃描時(shí)遇到開(kāi)始事件加一遇到結(jié)束事件減一過(guò)程中的最大值就是答案。這個(gè)“差分事件”的思路本質(zhì)上也是把區(qū)間降維成端點(diǎn)的組合。區(qū)間題學(xué)到這里你會(huì)發(fā)現(xiàn)大部分都能歸入“按右端點(diǎn)排序”或“按左端點(diǎn)排序合并”兩個(gè)套路。2.3 從二維到一維坐標(biāo)壓縮與差分?jǐn)?shù)組再往前一步有些區(qū)間問(wèn)題數(shù)量很大直接掃描時(shí)間軸會(huì)超時(shí)。這時(shí)候要用坐標(biāo)壓縮和差分?jǐn)?shù)組。講個(gè)我剛工作時(shí)遇到過(guò)的例子多個(gè)直播房間的預(yù)約表每個(gè)預(yù)約是一個(gè)起止時(shí)間段需要算出哪個(gè)時(shí)間段同時(shí)預(yù)約的房間數(shù)最多。如果時(shí)間范圍很大比如0到10^9直接開(kāi)一個(gè)數(shù)組記錄每個(gè)時(shí)刻的活躍數(shù)是不現(xiàn)實(shí)的。降維思路是這樣的把所有區(qū)間的端點(diǎn)收集起來(lái)排序去重得到一個(gè)壓縮后的坐標(biāo)軸區(qū)間長(zhǎng)度不重要重要的是端點(diǎn)之間的順序關(guān)系。然后在壓縮后的坐標(biāo)軸上做差分每個(gè)區(qū)間在左端點(diǎn)位置加一右端點(diǎn)位置或下一個(gè)位置減一最后前綴和一遍就能知道每個(gè)離散區(qū)間的覆蓋率。這樣整個(gè)數(shù)據(jù)規(guī)模從時(shí)間范圍降到了區(qū)間端點(diǎn)數(shù)乘2復(fù)雜度從O(T)變成O(n log n)。這種處理方式在貪心題的預(yù)處理階段非常常用。比如活動(dòng)安排需要判斷某個(gè)時(shí)刻能否插入新活動(dòng)比如任務(wù)調(diào)度需要統(tǒng)計(jì)某個(gè)截止時(shí)間前的已占用時(shí)間都可以先用差分?jǐn)?shù)組快速得到全局狀態(tài)。很多讀者覺(jué)得差分?jǐn)?shù)組是“數(shù)據(jù)結(jié)構(gòu)題”的內(nèi)容跟貪心無(wú)關(guān)其實(shí)不是。貪心算法經(jīng)常需要快速獲取“當(dāng)前全局狀態(tài)”差分?jǐn)?shù)組、前綴和、掃描線(xiàn)都是讓降維后的掃描保持高效的底層工具。3. 錯(cuò)位重構(gòu)當(dāng)標(biāo)準(zhǔn)貪心失效時(shí)怎么自救3.1 錯(cuò)位重構(gòu)不是玄學(xué)而是允許貪心先犯錯(cuò)標(biāo)準(zhǔn)貪心最大的缺陷是“一步錯(cuò)步步錯(cuò)”。因?yàn)槊恳徊蕉蓟诋?dāng)前局部最優(yōu)做決策一旦某一步的選擇不是全局最優(yōu)的一部分后面再怎么貪也補(bǔ)不回來(lái)。錯(cuò)位重構(gòu)這個(gè)思路就是主動(dòng)承認(rèn)“我的選擇順序可能錯(cuò)位”然后引入一種機(jī)制在后續(xù)掃描時(shí)把錯(cuò)誤的決策替換掉。它不是推翻整個(gè)貪心框架而是在貪心決策之后增加一個(gè)“糾偏操作”。我用一個(gè)非常直觀(guān)的例子來(lái)說(shuō)明。假設(shè)你要從一堆課程里選課每門(mén)課都有持續(xù)時(shí)間和截止日期你要在截止日期前完成課程才能算數(shù)目標(biāo)是選盡可能多的課。樸素貪心會(huì)想按截止日期排序能上就上。但這樣會(huì)出現(xiàn)問(wèn)題一門(mén)持續(xù)時(shí)間很長(zhǎng)的課占用了后續(xù)很多課程的時(shí)間明明可以為了多選幾門(mén)課而放棄它。這個(gè)場(chǎng)景里之前“上了課”的選擇就是錯(cuò)位的。錯(cuò)位重構(gòu)的解法很巧妙仍然按截止日期排序逐個(gè)嘗試加入當(dāng)前課程同時(shí)用一個(gè)最大堆保存已選課程的持續(xù)時(shí)間。每加入一門(mén)課后如果目前累計(jì)耗時(shí)超過(guò)了當(dāng)前課程的截止日期就把所有已選課程里耗時(shí)最長(zhǎng)的那門(mén)彈出。這樣等于在意識(shí)到“撐不住”時(shí)撤銷(xiāo)了之前那個(gè)最不劃算的選擇。整個(gè)過(guò)程依舊是一次掃描卻能把解從“局部最優(yōu)”提升到“全局最優(yōu)”。這種“先選進(jìn)去超限后踢出最差的”模式就是錯(cuò)位重構(gòu)最常見(jiàn)的實(shí)現(xiàn)。3.2 經(jīng)典場(chǎng)景課程選擇、股票交易、帶懲罰的任務(wù)調(diào)度除了課程選擇還有幾個(gè)高頻場(chǎng)景值得專(zhuān)門(mén)記一下。第一個(gè)是“股票交易II”的變體你可以無(wú)限次買(mǎi)賣(mài)但每次賣(mài)出要付手續(xù)費(fèi)。很多人第一反應(yīng)是“只要有利潤(rùn)就賣(mài)”但在有手續(xù)費(fèi)的情況下有時(shí)不賣(mài)反而更優(yōu)。這里就可以用錯(cuò)位重構(gòu)的思路維護(hù)一個(gè)“當(dāng)前最優(yōu)買(mǎi)入價(jià)”同時(shí)記錄“加上手續(xù)費(fèi)后賣(mài)出是否比之前的狀態(tài)更好”如果不賣(mài)更優(yōu)就保留原狀態(tài)。第二個(gè)是帶截止時(shí)間和利潤(rùn)的任務(wù)調(diào)度問(wèn)題每個(gè)任務(wù)有截止時(shí)間和完成利潤(rùn)同一時(shí)間只能做一個(gè)任務(wù)目標(biāo)是利潤(rùn)最大化。樸素貪心按利潤(rùn)從高到低排序然后嘗試把每個(gè)任務(wù)放到截止時(shí)間之前的空閑位置。這個(gè)解法本身不算錯(cuò)但如果任務(wù)數(shù)量很大逐個(gè)找空閑位置會(huì)很慢。錯(cuò)位重構(gòu)的變體是按截止時(shí)間從小到大掃描用一個(gè)最小堆維護(hù)已選任務(wù)的利潤(rùn)當(dāng)任務(wù)數(shù)超過(guò)當(dāng)前截止時(shí)間時(shí)彈出利潤(rùn)最小的任務(wù)。因?yàn)榻刂箷r(shí)間限制了最多能同時(shí)排多少個(gè)任務(wù)超過(guò)就必然要放棄一個(gè)放棄利潤(rùn)最小的總是最優(yōu)。第三個(gè)是“最多可以參加的會(huì)議數(shù)”和課程問(wèn)題幾乎一樣但日期離散化更明顯。你會(huì)發(fā)現(xiàn)這些場(chǎng)景都有一個(gè)共同結(jié)構(gòu)有一個(gè)限制條件截止時(shí)間、容量、資源上限每次貪心加入一個(gè)候選一旦候選集合超出限制就踢掉集合中價(jià)值最差的一個(gè)。這里的關(guān)鍵就是“用什么標(biāo)準(zhǔn)衡量最差”課程問(wèn)題踢掉耗時(shí)最長(zhǎng)任務(wù)調(diào)度踢掉利潤(rùn)最小完全由題目的目標(biāo)函數(shù)決定。3.3 堆是錯(cuò)位重構(gòu)的最佳載體選大還是選小錯(cuò)位重構(gòu)需要快速找到“該踢掉的那個(gè)”如果每次都用線(xiàn)性?huà)呙枵易钪祻?fù)雜度撐不住。所以這類(lèi)題的標(biāo)配是堆。但堆選型有個(gè)很容易記混的點(diǎn)什么時(shí)候用最大堆什么時(shí)候用最小堆我的記憶方法是這樣的加入候選后超過(guò)限制時(shí)要踢掉集合中最差的那一個(gè)所以“最差”的定義決定堆的方向。課程選擇里目標(biāo)是最大化課程數(shù)量那么占據(jù)時(shí)間最多的課程就是最差所以用最大堆保存持續(xù)時(shí)間踢堆頂。任務(wù)調(diào)度里目標(biāo)是最大化利潤(rùn)那么利潤(rùn)最低的任務(wù)就是最差所以用最小堆保存利潤(rùn)踢堆頂。反過(guò)來(lái)如果題目是“每個(gè)時(shí)刻選一個(gè)當(dāng)前收益最大的任務(wù)”那就是最小堆還是最大堆要視“保留最優(yōu)”還是“踢除最差”而定不要死記而是想清楚堆里裝的是已選集合我需要快速拿到哪個(gè)極值。堆之所以適合做錯(cuò)位重構(gòu)的載體是因?yàn)樗С帧跋扰R時(shí)接受再延遲否決”的機(jī)制。數(shù)組、棧都做不到在O(logn)內(nèi)動(dòng)態(tài)維護(hù)集合極值。前面我們提到貪心算法有時(shí)需要快速獲取全局狀態(tài)堆就是那個(gè)狀態(tài)維護(hù)器。而且錯(cuò)位重構(gòu)的思考順序也很重要先想清楚“當(dāng)前貪心決策可能錯(cuò)在哪里”再想“用什么數(shù)據(jù)結(jié)構(gòu)能修正它”。如果倒過(guò)來(lái)先想用什么堆很容易被數(shù)據(jù)結(jié)構(gòu)帶著走反而做不出正確策略。4. 實(shí)戰(zhàn)收官刪數(shù)問(wèn)題如何串起兩大思維4.1 題目描述與暴力解法帶來(lái)的直覺(jué)終于到今天的重頭戲刪數(shù)問(wèn)題。題目描述非常簡(jiǎn)單給定一個(gè)以字符串形式表示的非負(fù)整數(shù)num要求移除其中k個(gè)數(shù)字使得剩下的數(shù)字按原次序排列后形成的整數(shù)盡可能小。num可以很長(zhǎng)最多10^5位k小于num長(zhǎng)度。比如num 1432219k 3答案是1219num 10200k 1答案是200而不是0200因?yàn)榍皩?dǎo)零需要去掉最終把0200處理成200。這題在很多刷題平臺(tái)叫“移除K位數(shù)字”?？吹竭@個(gè)題第一反應(yīng)是暴力從n位里選k位刪掉共有C(n,k)種方案n一大直接爆炸。但暴力不是沒(méi)有價(jià)值。我建議讀者先寫(xiě)一個(gè)枚舉所有刪除方案的暴力程序?qū)﹄S機(jī)小數(shù)據(jù)生成答案然后用它來(lái)觀(guān)察一個(gè)規(guī)律。觀(guān)察后你會(huì)發(fā)現(xiàn)最優(yōu)解里被刪掉的數(shù)字幾乎都是“左邊數(shù)字大于右邊數(shù)字”的位置。比如1432219刪掉4、3、2這三個(gè)位置正好是每一輪當(dāng)前序列里第一個(gè)逆序?qū)Φ淖笤?。這個(gè)規(guī)律引出了經(jīng)典的貪心策略重復(fù)k次每次從左往右找到第一個(gè)滿(mǎn)足num[i] num[i1]的下標(biāo)i刪除num[i]。為什么刪除這個(gè)位置最優(yōu)因?yàn)楦呶粩?shù)字對(duì)數(shù)值大小的影響遠(yuǎn)大于低位從左往右第一個(gè)下降點(diǎn)就是“當(dāng)前最高位處第一次出現(xiàn)不增反降”把這個(gè)高位數(shù)刪掉能讓剩余序列的高位立刻變小。每次刪除都保證當(dāng)前這一步的收益最大而且這個(gè)收益不會(huì)被后續(xù)操作破壞因?yàn)楹罄m(xù)刪除都發(fā)生在更低位。4.2 棧優(yōu)化一次掃描完成所有逆序?qū)h除上面的策略每次都要從最左重新掃描復(fù)雜度是O(nk)在題目的數(shù)據(jù)范圍下不夠用。我們需要把“重復(fù)k次掃描找逆序點(diǎn)”的操作優(yōu)化成一次線(xiàn)性?huà)呙?。思路是把貪心過(guò)程壓縮到一個(gè)單調(diào)棧里從左到右遍歷每一位數(shù)字用一個(gè)棧保存“當(dāng)前保留的最優(yōu)前綴”每次遇到新數(shù)字時(shí)如果棧頂數(shù)字大于當(dāng)前數(shù)字并且還有剩余刪除次數(shù)就彈出棧頂這相當(dāng)于執(zhí)行了一次“刪除左側(cè)逆序?qū)Α钡牟僮?。為什么棧能等價(jià)替換原來(lái)的貪心因?yàn)槟莻€(gè)貪心每次刪除的是從左到右第一個(gè)逆序?qū)Φ淖笤囟鴹５膹棾霾僮魈烊话凑铡爱?dāng)前掃描到右邊更小的數(shù)字時(shí)左邊較大的數(shù)字先被刪除”的順序進(jìn)行正等價(jià)于從左到右處理逆序?qū)?。更妙的是如果一個(gè)數(shù)字彈出了棧說(shuō)明它再也不會(huì)進(jìn)入最終結(jié)果而如果掃描結(jié)束還有剩余刪除次數(shù)說(shuō)明序列已經(jīng)單調(diào)不減這時(shí)最優(yōu)策略就是刪除末尾的剩余位數(shù)讓最小的高位數(shù)字盡量保留。下面給出核心實(shí)現(xiàn)Pythondef remove_k_digits(num: str, k: int) - str: stack [] for ch in num: while stack and k 0 and stack[-1] ch: stack.pop() k - 1 stack.append(ch) # 如果還有剩余刪除次數(shù)刪掉末尾較大的數(shù)字 while k 0: stack.pop() k - 1 # 去掉前導(dǎo)零 res .join(stack).lstrip(0) return res if res else 0代碼非常短但每一個(gè)細(xì)節(jié)都有講究。比如彈出的條件必須是嚴(yán)格大于等于的時(shí)候不彈出因?yàn)閮蓚€(gè)相同的數(shù)字刪除左邊那個(gè)不會(huì)讓結(jié)果變小所以沒(méi)必要浪費(fèi)刪除次數(shù)。比如while循環(huán)里k要同時(shí)判斷防止多刪。比如最后要用lstrip(0)處理前導(dǎo)零如果全部刪空就返回0。4.3 邊界條件前導(dǎo)零、刪光、k為0刪數(shù)問(wèn)題的邊界條件是面試和筆試?yán)镒钊菀卓鄯值牡胤?。第一?lèi)邊界是前導(dǎo)零。原串里可能有0如果高位被刪除剩下的0會(huì)跑到最前面必須去掉。很多人忘記這一步導(dǎo)致10200刪除1位后輸出0200而不是200。注意lstrip(0)在Python里會(huì)把000變成空串所以要額外判斷空串返回0。第二類(lèi)邊界是k等于字符串長(zhǎng)度。此時(shí)要?jiǎng)h掉全部數(shù)字答案是什么題目通常規(guī)定“剩下的數(shù)字最小”既然全刪了就返回0。這個(gè)case要在代碼開(kāi)頭直接判斷或者依靠最后res if res else 0兜住但顯式判斷更清晰也方便寫(xiě)注釋。第三類(lèi)邊界是k0此時(shí)應(yīng)該原樣輸出但由于可能存在前導(dǎo)零的原輸入比如000123還是建議統(tǒng)一走一次處理邏輯。還有一類(lèi)細(xì)節(jié)是數(shù)字很長(zhǎng)直接用int會(huì)溢出或不必要所以全程保持字符串操作。這幾類(lèi)邊界我在對(duì)拍暴力程序時(shí)都踩過(guò)。最隱蔽的是“棧里所有數(shù)字已經(jīng)單調(diào)不減但k還沒(méi)用完”的情況很多人會(huì)忘記末尾刪除。其實(shí)只要想清楚單調(diào)不減序列里最小化結(jié)果應(yīng)該刪尾部刪頭部會(huì)讓更小的數(shù)字提前不會(huì)變優(yōu)但刪尾部不會(huì)改變高位所以尾部是相對(duì)最優(yōu)就不會(huì)漏掉這個(gè)while k0的循環(huán)。4.4 刪數(shù)問(wèn)題里的“降維”與“錯(cuò)位重構(gòu)”到底在哪現(xiàn)在把刪數(shù)問(wèn)題放回今天的主線(xiàn)。降維打擊體現(xiàn)在哪題目問(wèn)的是“刪除k個(gè)數(shù)字”這是一個(gè)組合選擇問(wèn)題選擇空間是C(n,k)非常恐怖。但我們通過(guò)觀(guān)察逆序?qū)Π阉稻S成一個(gè)“從左到右剪掉高峰”的掃描問(wèn)題每處理一個(gè)字符只需要決定當(dāng)前字符是否保留完全不需要關(guān)心后面那些還沒(méi)掃描到的字符的排列組合。這就是降維——把數(shù)百萬(wàn)種刪除組合壓成一次性的線(xiàn)性決策。錯(cuò)位重構(gòu)體現(xiàn)在哪看棧的工作方式就能感受到。遍歷到新數(shù)字ch時(shí)如果發(fā)現(xiàn)棧頂比ch大說(shuō)明之前把那個(gè)較大的數(shù)字保留進(jìn)棧是一個(gè)“錯(cuò)位”的選擇現(xiàn)在必須把它彈出去這個(gè)彈出過(guò)程本質(zhì)上是在撤銷(xiāo)之前的選擇。比如1432219走到第二個(gè)2時(shí)棧里的4和3都被彈出用2替代這就是對(duì)早期決策的重構(gòu)。貪心策略本身沒(méi)有變變成的只是允許已經(jīng)做出的選擇在后續(xù)被替換掉。所以我一直覺(jué)得刪數(shù)問(wèn)題是用棧實(shí)現(xiàn)的貪心同時(shí)也是用棧實(shí)現(xiàn)的反悔貪心兩者視角都對(duì)關(guān)鍵看你怎么理解它。5. 貪心題常見(jiàn)問(wèn)題與調(diào)試心得5.1 三個(gè)最常踩的坑先總結(jié)一下我在講解和刷題中看到的三個(gè)高頻坑。第一個(gè)坑是“沒(méi)有證明就開(kāi)寫(xiě)”。很多題目的樣例非常友好按直覺(jué)排序后樣例能過(guò)但隱藏?cái)?shù)據(jù)直接打臉。我自己的習(xí)慣是至少花三分鐘想一個(gè)反例想不出來(lái)再動(dòng)手實(shí)在想不出來(lái)就先寫(xiě)暴力對(duì)拍讓對(duì)拍結(jié)果來(lái)驗(yàn)證貪心。第二個(gè)坑是排序依據(jù)選錯(cuò)這在區(qū)間問(wèn)題里尤其明顯。同樣是區(qū)間活動(dòng)安排按右端點(diǎn)排序合并區(qū)間卻按左端點(diǎn)排序選錯(cuò)排序維度貪心直接失效。第三個(gè)坑是忽略邊界條件。刪數(shù)問(wèn)題的前導(dǎo)零只是其中之一更普遍的情況是輸入為空、所有元素都被刪光、k等于0、n等于1等。很多讀者代碼主體寫(xiě)對(duì)了卻在邊界上交了學(xué)費(fèi)。我在做對(duì)拍時(shí)發(fā)現(xiàn)邊界數(shù)據(jù)往往最能暴露貪心策略的缺陷因?yàn)樗鼤?huì)迫使你的代碼走到正常路徑之外的邏輯分支。建議每次提交前都想一遍算法在輸入極端小、結(jié)果極端空、目標(biāo)極端大時(shí)分別會(huì)做什么。5.2 調(diào)試貪心題的三板斧調(diào)試貪心題我常用的手段有三個(gè)按效率排序是小數(shù)據(jù)暴力對(duì)照、隨機(jī)對(duì)拍、打表觀(guān)察決策序列。小數(shù)據(jù)暴力對(duì)照是最快的驗(yàn)證方式把n控制在10以?xún)?nèi)暴力枚舉所有方案再跑你的貪心比較答案是否一致。隨機(jī)對(duì)拍是把小數(shù)據(jù)對(duì)照自動(dòng)化用腳本生成大量隨機(jī)測(cè)試樣例循環(huán)跑貪心和暴力一旦發(fā)現(xiàn)不一致就固定住那一組數(shù)據(jù)人工分析。我強(qiáng)烈建議每個(gè)貪心題都配一個(gè)對(duì)拍腳本它比任何代碼審查都靠譜。打表觀(guān)察決策序列是對(duì)拍發(fā)現(xiàn)錯(cuò)誤之后的第二步。不要只盯著答案不一致看把貪心每一步選了什么、決策時(shí)的狀態(tài)都打印出來(lái)。例如刪數(shù)問(wèn)題可以打印每次彈出哪個(gè)數(shù)字、剩余k是多少。你會(huì)發(fā)現(xiàn)錯(cuò)誤往往出現(xiàn)在“某個(gè)看似正確的局部選擇把后面的機(jī)會(huì)堵死了”。到這一步通常就能定位是貪心性質(zhì)不滿(mǎn)足還是堆的極值方向選反了。對(duì)拍腳本本身不復(fù)雜隨機(jī)生成輸入、調(diào)用兩個(gè)函數(shù)、比較輸出幾十行就能寫(xiě)完但它能省下大量在提交記錄里掙扎的時(shí)間。5.3 一套可復(fù)用的做題檢查清單最后我把這些年做貪心題沉淀下來(lái)的檢查清單分享給大家。每拿到一道貪心題按順序過(guò)一遍決策空間是什么如果選擇組合數(shù)很大思考能否用排序把決策順序固定下來(lái)。排序依據(jù)選哪個(gè)量選完之后能否用交換論證說(shuō)明“相鄰兩個(gè)決策的順序可以交換而不變差”。一次掃描中當(dāng)前決策是否會(huì)永久影響后續(xù)決策如果會(huì)思考是否允許“先接受、后反悔”。如果允許反悔用一個(gè)堆來(lái)動(dòng)態(tài)維護(hù)已選集合的最值并明確“最差”的定義。邊界條件有哪些空輸入、全部刪光、k為0、長(zhǎng)度1分別怎么處理。復(fù)雜度是否達(dá)標(biāo)能在線(xiàn)性?huà)呙柚型瓿删筒灰锥鄬友h(huán)。最后寫(xiě)一個(gè)暴力對(duì)拍跑至少幾百組隨機(jī)數(shù)據(jù)再提交。這套清單不是萬(wàn)能藥但它能幫你把一個(gè)模糊的“感覺(jué)能貪”變成可驗(yàn)證的“確實(shí)能貪”。我在帶新人時(shí)經(jīng)常說(shuō)貪心題考的不是聰明而是“能不能把直覺(jué)翻譯成可證明的策略”。多練幾道題之后你會(huì)發(fā)現(xiàn)在看到題目的前幾分鐘內(nèi)你已經(jīng)在心里默默執(zhí)行這套流程了。聊到這兒說(shuō)說(shuō)我自己的體會(huì)。刷了這么多年算法題貪心是我覺(jué)得“性?xún)r(jià)比”最高的一個(gè)專(zhuān)題因?yàn)榇a短、思維密度高但也是翻車(chē)率最高的專(zhuān)題。降維打擊和錯(cuò)位重構(gòu)這兩個(gè)詞是我自己總結(jié)出來(lái)的看待貪心的角度不一定是什么標(biāo)準(zhǔn)術(shù)語(yǔ)但它們確實(shí)幫我解決了很多“明明會(huì)做模板卻不會(huì)做題”的問(wèn)題。最后再分享一個(gè)小習(xí)慣每次做完一道貪心題寫(xiě)一句話(huà)總結(jié)它“為什么能貪”。積累幾十道之后你會(huì)發(fā)現(xiàn)貪心的套路真的就那么多剩下的全是證明功夫。