單調棧巧解柱狀圖最大矩形
- 2020 年 3 月 6 日
- 筆記
這幾天群里打卡的幾道題都是十分經典的面試題，經典是因為這些題都是一題多解的。在這些高效的解法中，單調棧是一個很有技巧的解法，所以這一次我們來聊聊這個單調棧。
所謂單調棧（Monotone Stack）聽上去很高端，其實就是字面的意思：棧內元素都是單調遞增或者單調遞減的。如上圖，就是一個從棧底到棧頂的單調遞增棧，當然還有另外一種就是單調遞減棧。你可能會想這種數據結構到底有什麼作用？其實這個數據結構並沒有任何高效操作，而是因為它在某些問題中是一個巧妙的解法。到底如何巧妙，我們下面來看兩道例題。
[LeetCode-84] 柱狀圖中最大的矩形
題目描述
給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。
以上是柱狀圖的示例，其中每個柱子的寬度為
1，給定的高度為[2,1,5,6,2,3]。
圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位。
示例輸入
輸入: [2,1,5,6,2,3] 輸出: 10
如何入手
首先來這麼考慮，「能夠勾勒出的最大矩形面積」 意味著如果我們可以枚舉所有的矩形大小，就可以找到最大的矩形面積。但是這最少需要 O(n^2) 的複雜度，也並不是我們想要的解答方法。
接下來我們想如何使用上文所說的單調棧來解決這個問題。
首先來考慮，這道題我們應該如何獲取到這幾塊矩形的面積？我們可以想到一個最簡單到邏輯，因為每一個顏色的矩形，其實都有一個觸頂的矩形。所以一個最簡單粗暴的思路就是枚舉每一個豎直方向的矩形，然後向兩邊擴展即可。但是這樣又會造成 O(n^2) 的開銷。
右側相鄰矩形永遠小於成塊矩形高度
繼續查看上面三個高亮的矩形，其實還有一個規律：所有的成塊矩形（使用圖表中某一個矩形向兩邊擴散圍成的最大矩形）後面的矩形，都會比成塊矩形高度要小。這是肯定的，因為如果要是大於等於，則還可以向右繼續擴展。我們發現了這個規律，再來觀察下面的兩幅圖。
為什麼我要把這兩個矩形挑出來，有一個很有趣的規律。我們注意到圖中具有高亮的這個矩形，都要比相鄰右側的矩形要高。所以我們完全可以猜想這兩個矩形可能是在同一時機被處理。也就是說，當我們從左向右遍歷矩形的時候，當發現 height[i] < height[i - 1] 的時候，我們會從 i 這個位置向左遍歷，直到找到第一個 height[j] < height[i] 的矩形，停止內層遍歷。在這個過程中，我們要不斷地更新結果，例如圖中的 A、B 這兩個情況。我們用動圖來描述一個這個情況：
計算面積
這只是我們猜想的一個規律，還有一些情況我們沒考慮到。拋開那個話題，先來看一個一般性問題：如何計算矩形面積？看上面的 B 圖，我們將高亮的地方單獨拿出來看。由於內層的遍歷，我們知道當前處理矩形的下標，所以根據夾閉的兩端下標以及當前處理的 j 矩形高度直接通過面積公式計算成塊矩形的面基。
遍歷次數並不是矩形寬度
繼續猜想，所以此時僅僅需要知道該矩形是第幾次遍歷，假設是第 K 次，那麼圍成的矩形面積即為 K * height[j]。我們似乎發現了一種通用規律，但其實離正確的做法還剩一步。到底最後的坑在哪裡，來看下面的這個例子。
當我們繼續遍歷到箭頭所指向的最後一個矩形的時候，我們繼續按照上面的規律來計算矩形。此時有兩個問題：
- B 情況與之前的 B 情況也是類似的場景，但是此時的 B 情況是其最佳解嗎？
- 為什麼遍歷五個矩形只出現了三種情況？還有情況 D 和情況 E 嗎？
問題 1
這個問題還是很好解決的，B 情況自然不是當前高度的最佳情況。因為有如下 B' 情況可使得其達到最佳狀況。
我為所有的矩形增加編號，讓下文的描述更清晰。其實發現的規律就是，5 號矩形高度所圍成的最大矩形情況其實是和 2 號矩形相關係的。為什麼？因為在上文中，當我加入 5 號的時候，3 號和 4 號的高度都比 5 號大，則以 3 號和 4 號高度的矩形情況我們已經處理完了，當後續矩形在二次遍歷的時候，3 號和 4 號的高度肯定是大於這個邊界矩形的。
此時你有沒有一種感覺，其實我們一直在維護一個單調遞增的序列，如果後續矩形的高度大於末尾，我們會反覆的進行計算，並且把末尾的矩形更新成新加入的矩形。這個感覺是對的，越來越逼近單調棧。
問題 2
如問題1 所描述的，此時 3 號和 4 號矩形已經是我們處理過的。其實我們可以把這個問題繼續轉化成 B'' 這種情況。
此圖中虛線代表已經處理過的矩陣，紫色代表加入我們處理序列的數組。我們來維護這個數組處於一個單調遞增的狀態，當遇到新的矩形高度小於末尾矩形的時候，就不斷的彈出末尾元素，進行剛才我們猜想的處理，直到找到第一個比它高度小的元素。
其實這就是在維護一個單調棧。
推導面積計算規律
再來看上面的 B' 情況，我們應該如何計算矩形 5 高度圍成的最大矩形面積呢？我用下圖來解釋：
這裡解釋一下圖中出現的幾個元素。棧即為本文所描述的單調棧，用來維護一個待處理矩形下標，並且矩形的高度是單調遞增的。當前處理矩形 i 代表最外層遍歷處理的矩形，由於圖中的 i 矩形高度是小於棧頂矩形高度的，所以開始進行彈棧操作。每一次彈棧的矩形是 cur 矩形，由於將要彈出，則進行一次以 cur 矩形高度為準的最大面積矩形的計算。
在圖中，我們給出了其計算公式，S = (i - stack[top] - 1) * height[cur] 。其中 (i - stack[top] - 1) 其實就是為了計算出矩形的長。為什麼是從 stack[top] 到 i - 1 呢？因為 cur 右側一直到 i - 1 號矩形都比 cur 要高，這是單調棧的特性。而 cur 到 stack[top] 之間雖然在棧中是沒有矩形的，卻是有距離的。如圖所示，3 號和 4 號矩形是我們之前相同方式彈出的兩個高矩形。這也就是為什麼我們需要記錄矩形的下標來入棧，其實是為了計算其長度。
動圖演示
圖示中我們使用上文中的那個矩形圖來作為用例，並且給每個矩形賦高度。則使用單調棧來解決這個最大面積，即為演示文稿中的方法求解。
剩餘棧的處理的 trick 方案
在圖中的演示中，我們發現到最後其實棧中還是有元素未處理完的，所以我們在使用單調棧場景的最後，要單調對棧中元素主動彈棧，並執行相同的查找面積最大值的邏輯。
但其實有一種更為 trick 的方案，就是我們主動在矩形圖的末尾增加一個高度為 0 的矩形，這樣棧在處理的時候就會主動彈棧，也就不用考慮處理剩餘棧的情況來。這種解決方案看似十分 trick，實際上單調棧的題目為了寫法方便，往往都會這麼做。
程式碼實現
知道了上述邏輯，就可以進行程式碼編寫了。這裡我用 Python 寫一版作為示例。
class Solution: def largestRectangleArea(self, heights) -> int: stack = [] # 前後插 0，處理余剩棧的情況 heights = [0] + heights + [0] n, res = len(heights), 0 for i in range(n): # 如果發現處理的矩形高度小於站頂矩形高度，則彈棧，通過上述方法來計算 while stack and heights[stack[-1]] > heights[i]: cur = stack.pop() res = max(res, (i - stack[-1] - 1) * heights[cur]) # 維護棧結構，保證單調遞增 stack.append(i) return res
總結經驗
其實單調棧的題目並不是很容易想到這個思路。目前我能總結到的只有多刷相關題目來提升熟練度。下面是我匯總的各個平台的單調棧專題，可以按照這個列表來刷。
- [LeetCode-42] 接雨水
- [LeetCode-239] 滑動窗口最大值
- [LeetCode-496] 下一個更大元素 I
- [LeetCode-503] 下一個更大元素 II
- [LeetCode-739] 每日溫度
- [LeetCode-901] 股票價格跨度
- [HDU-5749] Colmerauer
- [HDU-4252] A Famous City
- [HDU-1506] Largest Rectangle in a Histogram
- [HDU-6319] Ascending Rating
