摘要：也就是說我們只是知其然，并沒有知其所以然。相反，那些牛人就不會(huì)忘記自己設(shè)計(jì)的算法。劉未鵬在知其所以然三為什么算法這么難中探索了編碼的思維歷程，值得一看。之后，將當(dāng)前入棧，更新棧內(nèi)的遞增序列。

原文地址

相信大部分同學(xué)曾經(jīng)都學(xué)習(xí)過快速排序、Huffman、KMP、Dijkstra等經(jīng)典算法，初次學(xué)習(xí)時(shí)我們驚嘆于算法的巧妙，同時(shí)被設(shè)計(jì)者的智慧所折服。于是，我們仔細(xì)研讀算法的每一步，甚至去證明算法的正確性，或者是去嘗試優(yōu)雅地實(shí)現(xiàn)這些算法。總之，我們會(huì)花費(fèi)很大的時(shí)間精力去理解這些智慧的結(jié)晶。

然而，現(xiàn)在對于這些經(jīng)典的算法你仍然了然于胸嗎？就算現(xiàn)在你仍然記得這些算法的步驟，你敢確保一年后、十年后自己不會(huì)忘記？我想沒有多少人敢保證吧。

我們當(dāng)然希望自己掌握一個(gè)算法后，就永遠(yuǎn)不會(huì)忘記，最好還能舉一反三，利用算法中的思想去解決新的問題。然而，現(xiàn)實(shí)與美好的愿景往往是背道而馳，不要說舉一反三，我們甚至經(jīng)常忘記那些算法本身。

為什么會(huì)這樣？簡單來說，因?yàn)槲覀儚膩砭蜎]有真正掌握過這些算法，我們只不過是在背誦別人發(fā)明的算法，就像我們背誦歷史書上的那些歷史事件一樣，時(shí)間久了自然會(huì)慢慢遺忘。

我們接觸到某個(gè)算法時(shí)，看到的只是對算法過程的講解，對其正確性的證明，或者對其效率的分析（想想大名鼎鼎的《算法導(dǎo)論》，《算法》是如何講解某一算法的），我們不會(huì)看到那些牛人是如何“靈機(jī)一動(dòng)”設(shè)計(jì)出了這驚天地泣鬼神的算法。也就是說我們只是知其然，并沒有知其所以然。當(dāng)我們不知道一個(gè)算法的來龍去脈，不知道設(shè)計(jì)它經(jīng)歷的那些思維歷程時(shí)，就很容易忘記它的具體內(nèi)容。相反，那些牛人就不會(huì)忘記自己設(shè)計(jì)的算法。

所以，當(dāng)看到別人牛逼的閃閃發(fā)光的算法后，我們一定要探尋算法背后那“曲徑通幽”的思維之路。只有經(jīng)歷了思維之路的磨難，才配得上永遠(yuǎn)占有一個(gè)算法，并有可能舉一反三，或者是設(shè)計(jì)一個(gè)巧妙算法。劉未鵬在知其所以然（三）：為什么算法這么難？中探索了Huffman編碼的思維歷程，值得一看。順便說一下，探索算法背后的思維歷程不是件容易的事，要知道就是霍夫曼本人也是花了一個(gè)學(xué)期才想出它的編碼算法。

下面我們以LeetCode上一個(gè)好問題，來探索這個(gè)問題的算法背后的思維之路。關(guān)于什么是好問題，劉未鵬在跟波利亞學(xué)解題上有一個(gè)不錯(cuò)的觀點(diǎn)：好問題即測試一個(gè)人思維的習(xí)慣的題目，通?？疾炷愕穆?lián)想能力、類比能力、抽象能力、演繹能力、歸納能力、觀察能力、發(fā)散能力等。

LeetCode 84題：Largest Rectangle in Histogram，給定一個(gè)直方圖（下圖a），求直方圖中能夠組成的所有矩形中，面積最大為多少。對于圖a來說，我們很容易看出來面積最大的矩形為高度為5和6的直方圖組成的矩形（圖b隱形部分），其面積為5 * 2 = 10。

其實(shí)這個(gè)題稍微加以變化，就是另一個(gè)相當(dāng)有趣的問題：Maximal Rectangle.

這道題目一個(gè)顯而易見的解決方法就是暴力搜索：找出所有可能的矩形，然后求出面積最大的那個(gè)。要找出所有可能的矩形，只需要從左到右掃描每個(gè)立柱，然后以這個(gè)立柱為矩形的左邊界（假設(shè)為第i個(gè)），再向右掃面，分別以（i+1, i+2, n）為右邊界確定矩形的形狀。

這符合我們本能的思考過程：要找出最大的一個(gè)，就先列出所有的可能，比較大小后求出最大的那個(gè)。然而不幸的是，本能的思考過程通常是簡單粗暴而又低效的，就這個(gè)題目來說，時(shí)間復(fù)雜度為N^2 。那么有沒有一種更加高效的解決辦法呢？

我第一次面對這個(gè)題時(shí)，并沒有想出一個(gè)漂亮的解決方案。因?yàn)閺慕o定的條件來看，似乎找不到一個(gè)約束條件使得滿足這個(gè)條件的矩形面積最大，也就是說無法縮減問題的規(guī)模，因此必須找出所有可能的矩形，這樣的話效率肯定是N^2 。

然而去Google了一下，立即發(fā)現(xiàn)了一個(gè)時(shí)間復(fù)雜度O(n)的算法，當(dāng)時(shí)就被這神奇的解法所震撼到。它的代碼十分簡單，簡單到一開始我根本就看不懂，不明白為什么這樣子求出的就是最大的矩形。網(wǎng)上好多所謂的解題報(bào)告里面只是人云亦云地給出了算法的步驟，沒有算法正確性的證明，更沒有我們最想要的關(guān)于解題思路。

我也先給出算法步驟和代碼，看看你是不是同樣一頭霧水。在程序中維護(hù)一個(gè)棧，棧中元素為直方圖中bar的下標(biāo)，然后從頭開始掃描每個(gè)bar：

如果當(dāng)前bar的高度大于棧頂bar的高度，則將當(dāng)前bar的下標(biāo)入棧；

否則執(zhí)行出棧操作，記錄彈出下標(biāo)對應(yīng)的bar的高度，并計(jì)算出一個(gè)面積，然后用這個(gè)面積更新最大面積。

代碼也是相當(dāng)簡潔，python源碼如下：

def largestRectangleArea(self, height):
    height.append(0)
    size = len(height)
    no_decrease_stack = [0]
    max_size = height[0]

    i = 0
    while i < size:
        cur_num = height[i]
        if (not no_decrease_stack or
                cur_num > height[no_decrease_stack[-1]]):
            no_decrease_stack.append(i)
            i += 1
        else:
            index = no_decrease_stack.pop()
            if no_decrease_stack:
                width = i - no_decrease_stack[-1] - 1
            else:
                width = i
            max_size = max(max_size, width * height[index])

    return max_size

高效而難以理解，這就是那些神奇算法的共性。

那么這個(gè)算法真的就是我等凡夫俗子不能想出來的？難道我們只能仰望高山，恨自己智商不高？我還真不服氣呢，于是又靜下心去思考這個(gè)問題。

這次我們不從已知條件推結(jié)果，而直接從結(jié)論入手，就是說假設(shè)現(xiàn)在已經(jīng)找到了面積最大的那個(gè)矩形。接著我們來分析該矩形有什么特征，然后可以用下面兩種方法之一來縮減問題的規(guī)模（因?yàn)檫@兩種方法都不用找出所有的矩形一一比較）。

找出滿足這些特征的矩形，面積最大的矩形肯定是其中之一；

排除那些不滿足這些特征的矩形，面積最大的矩形在剩下的那些矩形里面。

為了使考慮情況盡可能全面，畫了許多直方圖，防止使用原題目圖片可能存在的一些特定假設(shè)，其中一個(gè)直方圖如下圖：

通過不斷地對多個(gè)直方圖的觀察，發(fā)現(xiàn)面積最大的那個(gè)矩形好像都包含至少一個(gè)完整的bar，那么這條規(guī)律適用于所有的直方圖嗎？我們用反證法來證明，假設(shè)某個(gè)最大矩形中每個(gè)豎直塊都是所在的bar的一小段，那么這個(gè)矩形高度增加1后仍然是一個(gè)合法的矩形，但新的矩形面積更大，與假設(shè)矛盾，所以面積最大的矩形必須至少有一個(gè)豎直塊是整個(gè)bar。

至此我們找到了面積最大矩形的一個(gè)特性：各組成豎直塊中至少有一個(gè)是完整的Bar。有了這條特性，我們再找面積最大的矩形時(shí)，就有了一個(gè)比較小的范圍。具體來說就是針對每個(gè)bar，我們找出包含這個(gè)bar的面積最大的矩形，然后只需要比較這N個(gè)矩形即可（N為bar的個(gè)數(shù)）。

那么問題又來了，如何找出“包含某個(gè)bar的面積最大的矩形呢”？對于上面的直方圖，包含下標(biāo)為4的bar的最大矩形如下圖橘黃色部分：

簡單觀察一下，就會(huì)發(fā)現(xiàn)要找到包含某個(gè)bar的最大矩形其實(shí)很簡答，只需要找到高度小于該bar的左、右邊界即可，上圖中分別是下標(biāo)為1的bar和下標(biāo)為10的bar。

至此問題已經(jīng)變?yōu)?strong>“對于給定的bar，如何確定高度比它小的左、右邊界”。其實(shí)求左邊界和右邊界是同樣的求法，下面我們考慮求每個(gè)bar的左邊界。最直接的思路是對于每個(gè)bar，掃面其前面所有的bar，找出最后一個(gè)高度小于它的bar，這樣的話時(shí)間復(fù)雜度明顯又是N^2 ，Holy Shit。

到這里似乎沒有路可走了，但如果我們繼續(xù)絞盡腦汁地去想，可能（或許你對棧理解的很深入，或許是你在一個(gè)類似的問題中用到了棧，當(dāng)然你也可能想到動(dòng)態(tài)規(guī)劃的思想，那也是可行的）會(huì)聯(lián)想到棧這一數(shù)據(jù)結(jié)構(gòu)。用棧維護(hù)一個(gè)高度遞增的bar的集合，也就是說棧底到棧頂部對應(yīng)的bar的高度越來越大。那么對應(yīng)一個(gè)剛讀入的bar，我們只需要比較它的高度和棧頂對應(yīng)bar的高度，如果當(dāng)前bar比較高，則彈出棧頂元素繼續(xù)比較，直到棧頂bar比它低或者棧為空。之后，將當(dāng)前bar入棧，更新棧內(nèi)的遞增序列。

我們從左到右掃一遍得到每個(gè)bar對應(yīng)的左邊界，然后從右到左掃一遍得到bar的右邊界。兩次掃描過程中，每個(gè)bar都只有出棧、入棧操作，所以時(shí)間復(fù)雜度為O(N)。通過這樣的預(yù)處理，即可以O(shè)(N)的時(shí)間復(fù)雜度得到每個(gè)bar的左右邊界。之后對于每個(gè)bar求出包含它的最大面積，也即是由左右邊界和bar的高度圍起來的矩形的面積。再做N次比較，即可得出最終的結(jié)果。

這里先預(yù)處理用兩個(gè)棧掃描兩次得到左、右邊界，再計(jì)算面積，是按照推導(dǎo)過程一步一步來的。當(dāng)我們寫完程序后，再綜合看這個(gè)問題，可能會(huì)發(fā)現(xiàn)其實(shí)沒必要這樣分開來做，我們可以在掃描的同時(shí)，維護(hù)一個(gè)遞增的棧，同時(shí)在“合適的”時(shí)候計(jì)算面積，然后更新最大面積。具體實(shí)現(xiàn)方法就是前面給出的那個(gè)神奇的算法，不過現(xiàn)在看來一點(diǎn)也不神奇了，我們已經(jīng)探索到了它背后的思維歷程。

當(dāng)然，條條道路通羅馬，上面思維過程只是其中一條通往解決方案的路徑，你可能以另一種思維過程找到了答案。不過，我們上面的整個(gè)推導(dǎo)過程沒有涉及一些類似“神諭”的啟發(fā)，只是一些簡單的方法：比如從結(jié)論推導(dǎo)、反證法、歸納總結(jié)、聯(lián)想（可能聯(lián)想到棧有點(diǎn)難）等，因此每個(gè)人都可以學(xué)會(huì)，并且很容易被大腦記住。值得注意的是，我們的整個(gè)思考過程并不簡簡單單地跟上面寫的那樣是線性的，它更可能是樹形的，只是我們剪去了那些后來證明行不通的枝。

人類在漫長的進(jìn)化史中，解決了各種各樣的問題。例如

如何度過一條湍急的河流

如何保留火種

如何治愈天花

如何制造一個(gè)會(huì)飛的機(jī)器

...

同時(shí)也對自己的思維方式進(jìn)行總結(jié)和反思，笛卡爾曾經(jīng)試圖將人類思維的規(guī)則總結(jié)為36條（最終完成了21條）。

那么有沒有一個(gè)解題的萬能思考法則，按照這個(gè)法則去思考，最終能解決所有的問題或者是證明某個(gè)問題不可解？目前看來是沒有這樣的思考法則的，不然我們就可以制造出真正的會(huì)思考的機(jī)器了。

不過還是有許多思維方法值得我們?nèi)W(xué)習(xí)強(qiáng)化，波利亞在《How To Solve It》上總結(jié)了這些方法，如果想培養(yǎng)良好的思維習(xí)慣，那么這本書是必不可少的。