相信大部分同學曾經都學習過快速排序、Huffman好港、KMP、Dijkstra等經典算法米罚，初次學習時我們驚嘆于算法的巧妙钧汹，同時被設計者的智慧所折服。于是录择，我們仔細研讀算法的每一步拔莱，甚至去證明算法的正確性，或者是去嘗試優(yōu)雅地實現(xiàn)這些算法隘竭√燎兀總之，我們會花費很大的時間精力去理解這些智慧的結晶动看。

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

我們當然希望自己掌握一個算法后京痢，就永遠不會忘記，最好還能舉一反三篷店，利用算法中的思想去解決新的問題祭椰。然而，現(xiàn)實與美好的愿景往往是背道而馳，不要說舉一反三，我們甚至經常忘記那些算法本身。

背算法與設計算法

為什么會這樣劈彪？簡單來說，因為我們從來就沒有真正掌握過這些算法橄霉，我們只不過是在背誦別人發(fā)明的算法，就像我們背誦歷史書上的那些歷史事件一樣邑蒋，時間久了自然會慢慢遺忘姓蜂。

我們接觸到某個算法時，看到的只是對算法過程的講解医吊，對其正確性的證明钱慢，或者對其效率的分析（想想大名鼎鼎的《算法導論》，《算法》是如何講解某一算法的）卿堂，我們不會看到那些牛人是如何“靈機一動”設計出了這驚天地泣鬼神的算法束莫。也就是說我們只是知其然，并沒有知其所以然草描。當我們不知道一個算法的來龍去脈览绿，不知道設計它經歷的那些思維歷程時，就很容易忘記它的具體內容穗慕。相反饿敲，那些牛人就不會忘記自己設計的算法。

所以逛绵，當看到別人牛逼的閃閃發(fā)光的算法后怀各，我們一定要探尋算法背后那“曲徑通幽”的思維之路。只有經歷了思維之路的磨難术浪，才配得上永遠占有一個算法瓢对，并有可能舉一反三，或者是設計一個巧妙算法胰苏。劉未鵬在知其所以然（三）：為什么算法這么難硕蛹？中探索了Huffman編碼的思維歷程，值得一看碟联。順便說一下妓美，探索算法背后的思維歷程不是件容易的事僵腺，要知道就是霍夫曼本人也是花了一個學期才想出它的編碼算法鲤孵。

下面我們以LeetCode上一個好問題，來探索這個問題的算法背后的思維之路辰如。關于什么是好問題普监，劉未鵬在跟波利亞學解題上有一個不錯的觀點：好問題即測試一個人思維的習慣的題目，通常考察你的聯(lián)想能力凯正、類比能力毙玻、抽象能力、演繹能力廊散、歸納能力桑滩、觀察能力、發(fā)散能力等允睹。

一個好問題

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

求直方圖最大面積矩形

其實這個題稍微加以變化，就是另一個相當有趣的問題：Maximal Rectangle.

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

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

一個好算法

我第一次面對這個題時钝鸽，并沒有想出一個漂亮的解決方案汇恤。因為從給定的條件來看，似乎找不到一個約束條件使得滿足這個條件的矩形面積最大拔恰，也就是說無法縮減問題的規(guī)模因谎，因此必須找出所有可能的矩形，這樣的話效率肯定是N^2 颜懊。

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

我也先給出算法步驟和代碼酿雪，看看你是不是同樣一頭霧水冰沙。在程序中維護一個棧，棧中元素為直方圖中bar的下標执虹，然后從頭開始掃描每個bar：

1. 如果當前bar的高度大于棧頂bar的高度拓挥，則將當前bar的下標入棧；
2. 否則執(zhí)行出棧操作袋励，記錄彈出下標對應的bar的高度侥啤，并計算出一個面積，然后用這個面積更新最大面積茬故。

代碼也是相當簡潔盖灸，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

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

一個思維歷程

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

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

1. 找出滿足這些特征的矩形，面積最大的矩形肯定是其中之一厢破；
2. 排除那些不滿足這些特征的矩形荣瑟，面積最大的矩形在剩下的那些矩形里面。

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

更一般的一個例子

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

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

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

一個面積

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

至此問題已經變?yōu)?strong>“對于給定的bar幔翰，如何確定高度比它小的左漩氨、右邊界”。其實求左邊界和右邊界是同樣的求法遗增，下面我們考慮求每個bar的左邊界才菠。最直接的思路是對于每個bar，掃面其前面所有的bar贡定，找出最后一個高度小于它的bar赋访，這樣的話時間復雜度明顯又是N^2 ，Holy Shit缓待。

到這里似乎沒有路可走了蚓耽，但如果我們繼續(xù)絞盡腦汁地去想，可能（或許你對棧理解的很深入旋炒，或許是你在一個類似的問題中用到了棧步悠，當然你也可能想到動態(tài)規(guī)劃的思想，那也是可行的）會聯(lián)想到棧這一數(shù)據(jù)結構瘫镇。用棧維護一個高度遞增的bar的集合鼎兽，也就是說棧底到棧頂部對應的bar的高度越來越大答姥。那么對應一個剛讀入的bar，我們只需要比較它的高度和棧頂對應bar的高度谚咬，如果當前bar比較高鹦付，則彈出棧頂元素繼續(xù)比較，直到棧頂bar比它低或者棧為空择卦。之后敲长，將當前bar入棧，更新棧內的遞增序列秉继。

我們從左到右掃一遍得到每個bar對應的左邊界祈噪，然后從右到左掃一遍得到bar的右邊界。兩次掃描過程中尚辑，每個bar都只有出棧辑鲤、入棧操作，所以時間復雜度為O(N)杠茬。通過這樣的預處理遂填，即可以O(N)的時間復雜度得到每個bar的左右邊界。之后對于每個bar求出包含它的最大面積澈蝙，也即是由左右邊界和bar的高度圍起來的矩形的面積吓坚。再做N次比較，即可得出最終的結果灯荧。

這里先預處理用兩個棧掃描兩次得到左礁击、右邊界，再計算面積逗载，是按照推導過程一步一步來的哆窿。當我們寫完程序后，再綜合看這個問題厉斟，可能會發(fā)現(xiàn)其實沒必要這樣分開來做挚躯，我們可以在掃描的同時，維護一個遞增的棧擦秽，同時在“合適的”時候計算面積码荔，然后更新最大面積。具體實現(xiàn)方法就是前面給出的那個神奇的算法感挥，不過現(xiàn)在看來一點也不神奇了缩搅，我們已經探索到了它背后的思維歷程。

當然触幼，條條道路通羅馬硼瓣，上面思維過程只是其中一條通往解決方案的路徑，你可能以另一種思維過程找到了答案置谦。不過堂鲤，我們上面的整個推導過程沒有涉及一些類似“神諭”的啟發(fā)亿傅，只是一些簡單的方法：比如從結論推導、反證法瘟栖、歸納總結葵擎、聯(lián)想（可能聯(lián)想到棧有點難）等，因此每個人都可以學會慢宗，并且很容易被大腦記住坪蚁。值得注意的是奔穿，我們的整個思考過程并不簡簡單單地跟上面寫的那樣是線性的镜沽，它更可能是樹形的，只是我們剪去了那些后來證明行不通的枝贱田。

解題的萬能思考法則?

人類在漫長的進化史中缅茉，解決了各種各樣的問題。例如

• 如何度過一條湍急的河流
• 如何保留火種
• 如何治愈天花
• 如何制造一個會飛的機器
• ...

同時也對自己的思維方式進行總結和反思男摧，笛卡爾曾經試圖將人類思維的規(guī)則總結為36條（最終完成了21條）蔬墩。

那么有沒有一個解題的萬能思考法則，按照這個法則去思考耗拓，最終能解決所有的問題或者是證明某個問題不可解拇颅？目前看來是沒有這樣的思考法則的，不然我們就可以制造出真正的會思考的機器了乔询。

不過還是有許多思維方法值得我們去學習強化樟插，波利亞在《How To Solve It》上總結了這些方法，如果想培養(yǎng)良好的思維習慣竿刁，那么這本書是必不可少的黄锤。

更多文章，請移步我的博客