# 0084. 柱狀圖中最大的矩形 ## 題目地址（84. 柱狀圖中最大的矩形） <https://leetcode-cn.com/problems/largest-rectangle-in-histogram/> ## 題目描述 給定 n 個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為 1 。 求在該柱狀圖中，能夠勾勒出來的矩形的最大面積。  以上是柱狀圖的示例，其中每個柱子的寬度為 1，給定的高度為 \[2,1,5,6,2,3\]。  圖中陰影部分為所能勾勒出的最大矩形面積，其面積為 10 個單位。 ``` <pre class="calibre18">``` 示例： 輸入：[2,1,5,6,2,3] 輸出：10 ``` ``` ## 前置知識 - 單調棧 ## 暴力枚舉 - 左右端點法（TLE） ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ### 思路 我們暴力嘗試`所有可能的矩形`。由于矩陣是二維圖形， 我我們可以使用`左右兩個端點來唯一確認一個矩陣`。因此我們使用雙層循環枚舉所有的可能性即可。 而矩形的面積等于`（右端點坐標 - 左端點坐標 + 1) * 最小的高度`，最小的高度我們可以在遍歷的時候順便求出。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n, ans = len(heights), <span class="hljs-params">0</span> <span class="hljs-keyword">if</span> n != <span class="hljs-params">0</span>: ans = heights[<span class="hljs-params">0</span>] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): height = heights[i] <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i, n): height = min(height, heights[j]) ans = max(ans, (j - i + <span class="hljs-params">1</span>) * height) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N^2)O(N2) - 空間復雜度：O(1)O(1)O(1) ## 暴力枚舉 - 中心擴展法（TLE） ### 思路 我們仍然暴力嘗試`所有可能的矩形`。只不過我們這一次從中心向兩邊進行擴展。對于每一個 i，我們計算出其左邊第一個高度小于它的索引 p，同樣地，計算出右邊第一個高度小于它的索引 q。那么以 i 為最低點能夠構成的面積就是`(q - p - 1) * heights[i]`。 這種算法毫無疑問也是正確的。 我們證明一下，假設 f(i) 表示求以 i 為最低點的情況下，所能形成的最大矩陣面積。那么原問題轉化為`max(f(0), f(1), f(2), ..., f(n - 1))`。 具體算法如下： - 我們使用 l 和 r 數組。l\[i\] 表示 左邊第一個高度小于它的索引，r\[i\] 表示 右邊第一個高度小于它的索引。 - 我們從前往后求出 l，再從后往前計算出 r。 - 再次遍歷求出所有的可能面積，并取出最大的。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n = len(heights) l, r, ans = [<span class="hljs-params">-1</span>] * n, [n] * n, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): j = i - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j -= <span class="hljs-params">1</span> l[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">2</span>, <span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>): j = i + <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j < n <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j += <span class="hljs-params">1</span> r[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): ans = max(ans, heights[i] * (r[i] - l[i] - <span class="hljs-params">1</span>)) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度：O(N2)O(N^2)O(N2) - 空間復雜度：O(N)O(N)O(N) ## 優化中心擴展法（Accepted） ### 思路 實際上我們內層循環沒必要一步一步移動，我們可以直接將`j -= 1` 改成 `j = l[j]`, `j += 1` 改成 `j = r[j]`。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n = len(heights) l, r, ans = [<span class="hljs-params">-1</span>] * n, [n] * n, <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-params">1</span>, n): j = i - <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j >= <span class="hljs-params">0</span> <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j = l[j] l[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n - <span class="hljs-params">2</span>, <span class="hljs-params">-1</span>, <span class="hljs-params">-1</span>): j = i + <span class="hljs-params">1</span> <span class="hljs-keyword">while</span> j < n <span class="hljs-keyword">and</span> heights[j] >= heights[i]: j = r[j] r[i] = j <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n): ans = max(ans, heights[i] * (r[i] - l[i] - <span class="hljs-params">1</span>)) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) ## 單調棧（Accepted） ### 思路 實際上，讀完第二種方法的時候，你應該注意到了。我們的核心是求左邊第一個比 i 小的和右邊第一個比 i 小的。 如果你熟悉單調棧的話，那么應該會想到這是非常適合使用單調棧來處理的場景。 從左到右遍歷柱子，對于每一個柱子，我們想找到第一個高度小于它的柱子，那么我們就可以使用一個單調遞增棧來實現。 如果柱子大于棧頂的柱子，那么說明不是我們要找的柱子，我們把它塞進去繼續遍歷，如果比棧頂小，那么我們就找到了第一個小于的柱子。 **對于棧頂元素，其右邊第一個小于它的就是當前遍歷到的柱子，左邊第一個小于它的就是棧中下一個要被彈出的元素**，因此以當前棧頂為最小柱子的面積為**當前棧頂的柱子高度 \* (當前遍歷到的柱子索引 - 1 - 棧中下一個要被彈出的元素索引 - 1 + 1)** 這種方法只需要遍歷一次，并用一個棧。由于每一個元素最多進棧出棧一次，因此時間和空間復雜度都是O(N)O(N)O(N)。 為了統一算法邏輯，減少邊界處理，我在 heights 首尾添加了兩個哨兵元素，**這樣我們可以保證所有的柱子都會出棧**。 ### 代碼 ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n, heights, st, ans = len(heights), [<span class="hljs-params">0</span>] + heights + [<span class="hljs-params">0</span>], [], <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n + <span class="hljs-params">2</span>): <span class="hljs-keyword">while</span> st <span class="hljs-keyword">and</span> heights[st[<span class="hljs-params">-1</span>]] > heights[i]: ans = max(ans, heights[st.pop(<span class="hljs-params">-1</span>)] * (i - st[<span class="hljs-params">-1</span>] - <span class="hljs-params">1</span>)) st.append(i) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 2020-05-30 更新： 有的觀眾反應看不懂為啥需要兩個哨兵。 其實末尾的哨兵就是為了將棧清空，防止遍歷完成棧中還有沒參與運算的數據。 而前面的哨兵有什么用呢？ 我這里把上面代碼進行了拆解： ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">largestRectangleArea</span><span class="hljs-params">(self, heights: List[int])</span> -> int:</span> n, heights, st, ans = len(heights),[<span class="hljs-params">0</span>] + heights + [<span class="hljs-params">0</span>], [], <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n + <span class="hljs-params">2</span>): <span class="hljs-keyword">while</span> st <span class="hljs-keyword">and</span> heights[st[<span class="hljs-params">-1</span>]] > heights[i]: a = heights[st[<span class="hljs-params">-1</span>]] <span class="hljs-title"># 如果沒有前面的哨兵，這里可能會越界。</span> st.pop() ans = max(ans, a * (i - <span class="hljs-params">1</span> - st[<span class="hljs-params">-1</span>])) st.append(i) <span class="hljs-keyword">return</span> ans ``` ``` ## 相關題目 - [42.trapping-rain-water](https://github.com/azl397985856/leetcode/blob/master/problems/42.trapping-rain-water.md) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的 LeetCode 題解