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