知其所以然之永不遺忘的算法
相信大部分同學曾經都學習過快速排序、Huffman、KMP、Dijkstra等經典算法，初次學習時我們驚嘆于算法的巧妙，同時被設計者的智 慧所折服。于是，我們仔細研讀算法的每一步，甚至去證明算法的正確性，或者是去嘗試優雅地實現這些算法。總之，我們會花費很大的時間精力去理解這些智慧的 結晶。
然而，現在對于這些經典的算法你仍然了然于胸嗎？就算現在你仍然記得這些算法的步驟，你敢確保一年后、十年后自己不會忘記？我想沒有多少人敢保證吧。
我們當然希望自己掌握一個算法后，就永遠不會忘記，最好還能舉一反三，利用算法中的思想去解決新的問題。然而，現實與美好的愿景往往是背道而馳，不要說舉一反三，我們甚至經常忘記那些算法本身。
背算法與設計算法
為什么會這樣？簡單來說，因為我們從來就沒有真正掌握過這些算法，我們只不過是在 背誦 別人發明的算法，就像我們背誦歷史書上的那些歷史事件一樣，時間久了自然會慢慢遺忘。
我們接觸到某個算法時，看到的只是對算法過程的講解，對其正確性的證明，或者對其效率的分析（想想大名鼎鼎的《算法導論》，《算法》是如何講解某一算法的），我們不會看到那些牛人是如何“ 靈機一動 ”設計出了這驚天地泣鬼神的算法。也就是說我們只是知其然，并沒有知其所以然。當我們不知道一個算法的來龍去脈，不知道設計它經歷的那些思維歷程時，就很容易忘記它的具體內容。相反，那些牛人就不會忘記自己設計的算法。
所以，當看到別人牛逼的閃閃發光的算法后，我們一定要探尋算法背后那“曲徑通幽”的思維之路。只有經歷了思維之路的磨難，才配得上永遠占有一個算法，并有可能舉一反三，或者是設計一個巧妙算法。劉未鵬在 知其所以然（三）：為什么算法這么難？ 中探索了Huffman編碼的思維歷程，值得一看。順便說一下，探索算法背后的思維歷程不是件容易的事，要知道就是霍夫曼本人也是花了一個學期才想出它的編碼算法。
下面我們以LeetCode上一個 好問題 ，來探索這個問題的算法背后的思維之路。關于什么是好問題，劉未鵬在 跟波利亞學解題 上有一個不錯的觀點： 好問題即測試一個人思維的習慣的題目 ，通常考察你的聯想能力、類比能力、抽象能力、演繹能力、歸納能力、觀察能力、發散能力等。
一個好問題
LeetCode 84題： Largest Rectangle in Histogram ，給定一個直方圖（下圖a），求直方圖中能夠組成的所有矩形中，面積最大為多少。對于圖a來說，我們很容易看出來面積最大的矩形為高度為5和6的直方圖組成的矩形（圖b隱形部分），其面積為5 * 2 = 10。
求直方圖最大面積矩形
其實這個題稍微加以變化，就是另一個相當有趣的問題：Maximal Rectangle.
這道題目一個顯而易見的解決方法就是 暴力搜索 ：找出所有可能的矩形，然后求出面積最大的那個。要找出所有可能的矩形，只需要從左到右掃描每個立柱，然后以這個立柱為矩形的左邊界（假設為第i個），再向右掃面，分別以（i+1, i+2, n）為右邊界確定矩形的形狀。
這符合我們本能的思考過程：要找出最大的一個，就先列出所有的可能，比較大小后求出最大的那個。然而不幸的是，本能的思考過程通常是簡單粗暴而又低效的，就這個題目來說，時間復雜度為N^2 。那么有沒有一種更加高效的解決辦法呢？
一個好算法
我第一次面對這個題時，并沒有想出一個漂亮的解決方案。因為從給定的條件來看，似乎找不到一個約束條件使得滿足這個條件的矩形面積最大，也就是說無法縮減問題的規模，因此必須找出所有可能的矩形，這樣的話效率肯定是N^2 。
然而去Google了一下，立即發現了一個時間復雜度O(n)的算法，當時就被這神奇的解法所震撼到。它的代碼十分簡單，簡單到一開始我根本就看 不懂，不明白為什么這樣子求出的就是最大的矩形。網上好多所謂的解題報告里面只是人云亦云地給出了算法的步驟，沒有算法正確性的證明，更沒有我們最想要的 關于解題思路。
我也先給出算法步驟和代碼，看看你是不是同樣一頭霧水。在程序中維護一個棧，棧中元素為直方圖中bar的下標，然后從頭開始掃描每個bar：
- 如果當前bar的高度大于棧頂bar的高度，則將當前bar的下標入棧；
- 否則執行出棧操作，記錄彈出下標對應的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高效而難以理解，這就是那些神奇算法的共性。
一個思維歷程
那么這個算法真的就是我等凡夫俗子不能想出來的？難道我們只能仰望高山，恨自己智商不高？我還真不服氣呢，于是又靜下心去思考這個問題。
這次我們不從已知條件推結果，而直接從結論入手，就是說假設現在已經找到了面積最大的那個矩形。接著我們來分析該矩形有什么特征，然后可以用下面兩種方法之一來縮減問題的規模（因為這兩種方法都不用找出所有的矩形一一比較）。
- 找出滿足這些特征的矩形，面積最大的矩形肯定是其中之一；
- 排除那些不滿足這些特征的矩形，面積最大的矩形在剩下的那些矩形里面。
為了使考慮情況盡可能全面，畫了許多直方圖，防止使用原題目圖片可能存在的一些特定假設，其中一個直方圖如下圖：
更一般的一個例子
通過不斷地對多個直方圖的觀察，發現面積最大的那個矩形好像都包含至少一個完整的bar，那么這條規律適用于所有的直方圖嗎？我們用反證法來證 明，假設某個最大矩形中每個豎直塊都是所在的bar的一小段，那么這個矩形高度增加1后仍然是一個合法的矩形，但新的矩形面積更大，與假設矛盾，所以面積 最大的矩形必須至少有一個豎直塊是整個bar。
至此我們找到了面積最大矩形的一個特性： 各組成豎直塊中至少有一個是完整的Bar 。有了這條特性，我們再找面積最大的矩形時，就有了一個比較小的范圍。具體來說就是針對每個bar，我們找出包含這個bar的面積最大的矩形，然后只需要比較這N個矩形即可（N為bar的個數）。
那么問題又來了，如何找出“ 包含某個bar的面積最大的矩形呢 ”？對于上面的直方圖，包含下標為4的bar的最大矩形如下圖橘黃色部分：
簡單觀察一下，就會發現要找到包含某個bar的最大矩形其實很簡答，只需要找到高度小于該bar的左、右邊界即可，上圖中分別是下標為1的bar和下標為10的bar。
至此問題已經變為 “對于給定的bar，如何確定高度比它小的左、右邊界” 。其實求左邊界和右邊界是同樣的求法，下面我們考慮求每個bar的左邊界。最直接的思路是對于每個bar，掃面其前面所有的bar，找出最后一個高度小于它的bar，這樣的話時間復雜度明顯又是N^2 ，Holy Shit。
到這里似乎沒有路可走了，但如果我們繼續絞盡腦汁地去想， 可能 （或許你對棧理解的很深入，或許是你在一個類似的問題中用到了棧，當然你也可能想到動態規劃的思想，那也是可行的）會 聯想 到 棧 這一數據結構。 用棧維護一個高度遞增的bar的集合，也就是說棧底到棧頂部對應的bar的高度越來越大 。那么對應一個剛讀入的bar，我們只需要比較它的高度和棧頂對應bar的高度，如果當前bar比較高，則彈出棧頂元素繼續比較，直到棧頂bar比它低或者棧為空。之后，將當前bar入棧，更新棧內的遞增序列。
我們從左到右掃一遍得到每個bar對應的左邊界，然后從右到左掃一遍得到bar的右邊界。兩次掃描過程中，每個bar都只有出棧、入棧操作，所以 時間復雜度為O(N)。通過這樣的預處理，即可以O(N)的時間復雜度得到每個bar的左右邊界。之后對于每個bar求出包含它的最大面積，也即是由左右 邊界和bar的高度圍起來的矩形的面積。再做N次比較，即可得出最終的結果。
這里先預處理用兩個棧掃描兩次得到左、右邊界，再計算面積，是按照推導過程一步一步來的。當我們寫完程序后，再綜合看這個問題，可能會發現其實沒 必要這樣分開來做，我們可以在掃描的同時，維護一個遞增的棧，同時在“合適的”時候計算面積，然后更新最大面積。具體實現方法就是前面給出的那個神奇的算 法，不過現在看來一點也不神奇了，我們已經探索到了它背后的思維歷程。
當然，條條道路通羅馬，上面思維過程只是其中一條通往解決方案的路徑，你可能以另一種思維過程找到了答案。不過，我們上面的整個推導過程沒有涉及 一些類似“神諭”的啟發，只是一些簡單的方法：比如從結論推導、反證法、歸納總結、聯想（可能聯想到棧有點難）等，因此每個人都可以學會，并且很容易被大 腦記住。值得注意的是，我們的整個思考過程并不簡簡單單地跟上面寫的那樣是線性的，它更可能是樹形的，只是我們剪去了那些后來證明行不通的枝。
解題的萬能思考法則?
人類在漫長的進化史中，解決了各種各樣的問題。例如
- 如何度過一條湍急的河流
- 如何保留火種
- 如何治愈天花
- 如何制造一個會飛的機器
- ...
同時也對自己的思維方式進行總結和反思，笛卡爾曾經試圖將人類思維的規則總結為36條（最終完成了21條）。
那么有沒有一個解題的萬能思考法則，按照這個法則去思考，最終能解決所有的問題或者是證明某個問題不可解？目前看來是沒有這樣的思考法則的，不然我們就可以制造出真正的會思考的機器了。
不過還是有許多思維方法值得我們去學習強化，波利亞在《How To Solve It》上總結了這些方法，如果想培養良好的思維習慣，那么這本書是必不可少的。