# 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 题解