[演算法] Largest Rectangle in Histogram 筆記
這個題目是想求一連串的直方圖中，所能形成最大的長方形，示意圖如下，蠻清楚的表示出在各種可能的長方形中，斜線範圍面積就是我們想要的結果
除了暴力法之外，要如何有效地解決這個問題呢？做筆記就是對看到的解法表達我誠摯的尊敬，對於我個人實在是覺得…神奇啊
神奇的解法利用了堆疊 (stack) 來存放一個單調遞增數列的位置，然後反覆地計算可能的最大值。有兩個部分可以先來好好思考，以方便理解最後的實作。首先就是為什麼要保留單調遞增數列呢？這樣的型態對於這個問題有什麼特性？好的演算法來自於對問題的深入理解，在日常生活或是商業模式中也是這個道理，理解需求與問題更有助於提出有效或更好的解決方案，但往往最難的也是這個部分，這是學習到目前的粗淺心得。
那我們觀察一下上面題目的示意圖，如果最大長方形的左邊邊界位置叫做 index_left，右邊邊界位置叫做 index_right，在這樣雜亂無章的形狀中，兩個位置共有 n*(n+1)/2 個選擇，直接窮舉的運算量挺大，但如果我們面對的是一個單調的遞增型態如下，事情就會比較簡單：
由於最後一根高度會大於前面所有的高度，所以最後一根之前的最大長方形(藍、黃、紅)，一定可以跟最後一根圍成更大的長方形，然後與最後一根自己形成的長方形(紫)比大小，看誰才是最大。無論如何，index_right 都固定在最後一根，所以比較各個面積時，調整 index_left 的計算量只有 n 種
腦洞再調大一點點，如果只比較這四種 index_left 不一樣的最大面積，這幾根不一定要連續在一起，前提是中間的部分(灰色點點)高度會高於黃色那根，這個想法先記起來
接下來筆記實作的主要想法，我們會保持一個 stack 來記錄單調遞增的位置，直到遇到一根比較矮的小夥伴(紫)
這時候我們計算一些符合條件的長方形面積，什麼條件呢？就是 index_right 固定在小夥伴(紫)的前一根(紅)，而且所有比小夥伴高的柱狀形成的長方形面積，以上圖來說就是紅色與黃色部份，會不會超過目前紀錄的最大面積。
心裡馬上跳出來的一個問題是，為什麼只算比小夥伴高的柱狀呢？可以這樣無視前面那兩根的存在嗎，給點尊重不好嗎這位…恩不是，我們再進入第二層思考可以發現，那些比小夥伴矮的柱狀，其實是可以跟小夥伴形成更大的長方形，所以我們還先不要去算他們，也就是如下圖，可以跟小夥伴形成綠色跟藍色的長方形
接著，當我們在小夥伴後面遇到更小夥伴的時候，index_right 移到之前的紫色小夥伴身上，然後前面沒算到的那些面積，就可以在這時候計算可能的最大長方形，也就是綠色跟藍色的面積(回頭看一下上面開腦洞的地方，去掉了黃色跟紅色高個，這個遞增數列可以不用實際緊密排列在一起)
沒錯，解法上會從 stack pop 掉紅色跟黃色兩根的位置，然後放入紫色小夥伴，還是形成一個單調遞增數列。因為我們需要長方形的寬度去計算，所以 stack 裡面存的是每一根的位置，而 index_right 減掉存的位置就是寬度(這部分請見下方程式碼體驗一下會比較有感覺)。當然紫色後面的夥伴可能更高，就繼續放進去遞增數列，index_right 往後移，這時候再遇到更後面的小夥伴時候，index_right 就會是最高的夥伴，而減少計算 index_right 在紫色身上的長方形，因為不需要。這個巧妙的故事不長，卻值得花時間好好思考
參考網路文章寫的程式碼，不算 function 名字只有十行！對這個題目跟思考方式再次表達我誠摯的敬意。如果有任何回饋或指點都非常歡迎，喜歡這篇的話也可以拍拍手按個讚，讓我知道這條路上總有夥伴 XD，謝謝～
