# 0085. 最大矩形 ## 題目地址（85. 最大矩形） <https://leetcode-cn.com/problems/maximal-rectangle/> ## 題目描述 給定一個僅包含 0 和 1 的二維二進制矩陣，找出只包含 1 的最大矩形，并返回其面積。 示例： 輸入： ``` <pre class="calibre18">``` [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] ``` ``` 輸出：6 ## 前置知識 - 單調棧 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 我在 [【84. 柱狀圖中最大的矩形】多種方法（Python3）](https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-zhu-zhuang-tu-zhong-zui-da-de-ju-xing-duo-chong/ "【84. 柱狀圖中最大的矩形】多種方法（Python3）") 使用了多種方法來解決。 然而在這道題，我們仍然可以使用完全一樣的思路去完成。 不熟悉的可以看下我的題解。本題解是基于那道題的題解來進行的。 拿題目給的例子來說： ``` <pre class="calibre18">``` [ ["1","0","1","0","0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] ``` ``` 我們逐行掃描得到 `84. 柱狀圖中最大的矩形` 中的 heights 數組：  這樣我們就可以使用`84. 柱狀圖中最大的矩形` 中的解法來進行了，這里我們使用單調棧來解。 ## 代碼 ``` <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 <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maximalRectangle</span><span class="hljs-params">(self, matrix: List[List[str]])</span> -> int:</span> m = len(matrix) <span class="hljs-keyword">if</span> m == <span class="hljs-params">0</span>: <span class="hljs-keyword">return</span> <span class="hljs-params">0</span> n = len(matrix[<span class="hljs-params">0</span>]) heights = [<span class="hljs-params">0</span>] * n ans = <span class="hljs-params">0</span> <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(m): <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(n): <span class="hljs-keyword">if</span> matrix[i][j] == <span class="hljs-string">"0"</span>: heights[j] = <span class="hljs-params">0</span> <span class="hljs-keyword">else</span>: heights[j] += <span class="hljs-params">1</span> ans = max(ans, self.largestRectangleArea(heights)) <span class="hljs-keyword">return</span> ans ``` ``` **復雜度分析** - 時間復雜度：O(M?N)O(M \* N)O(M?N) - 空間復雜度：O(N)O(N)O(N) 歡迎關注我的公眾號《腦洞前端》獲取更多更新鮮的 LeetCode 題解