【面试高频题】难度 2/5，HOT 100 级别的单调栈运用题

朴灿烈づ我的快乐病毒、 2023-10-10 20:33 24阅读 0赞

给定 `n` 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 `1` 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

![format_png][]

ini

复制代码

`输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10`

示例 2：

![format_png 1][]

ini

复制代码

`输入： heights = [2,4] 输出： 4`

提示：

*  1<=heights.length<=1051 <= heights.length <=10^51<=heights.length<=105
 *  0<=heights\[i\]<=1040 <= heights\[i\] <= 10^40<=heights\[i\]<=104

### 单调栈 + 枚举高度 ###

为了方便，我们令 `heights` 为 `hs`。

最终矩形的高度必然取自某个 hs\[i\]hs\[i\]hs\[i\]，因此我们可以枚举最终矩形的高度来做。

问题转换为当使用某个 hs\[i\]hs\[i\]hs\[i\] 作为矩形高度时，该矩形所能取得的最大宽度为多少。

假设我们能够预处理出 `l` 和 `r` 数组，其中 l\[i\]l\[i\]l\[i\] 代表位置 iii 左边最近一个比其小的位置（初始值为 −1-1−1），r\[i\]r\[i\]r\[i\] 代表位置 iii 右边最近一个比其小的位置（初始值为 nnn），那么 r\[i\]−l\[i\]−1r\[i\] - l\[i\] - 1r\[i\]−l\[i\]−1 则是以 hs\[i\]hs\[i\]hs\[i\] 作为矩形高度时所能取得的最大宽度。

预处理 `l` 和 `r` 则是经典的「求最近一个比当前值大的位置」单调栈问题。

Java 代码：

Java

复制代码

`class Solution { public int largestRectangleArea(int[] hs) { int n = hs.length; int[] l = new int[n], r = new int[n]; Arrays.fill(l, -1); Arrays.fill(r, n); Deque<Integer> d = new ArrayDeque<>(); for (int i = 0; i < n; i++) { while (!d.isEmpty() && hs[d.peekLast()] > hs[i]) r[d.pollLast()] = i; d.addLast(i); } d.clear(); for (int i = n - 1; i >= 0; i--) { while (!d.isEmpty() && hs[d.peekLast()] > hs[i]) l[d.pollLast()] = i; d.addLast(i); } int ans = 0; for (int i = 0; i < n; i++) { int t = hs[i], a = l[i], b = r[i]; ans = Math.max(ans, (b - a - 1) * t); } return ans; } }`

TypeScript 代码：

TypeScript

复制代码

`function largestRectangleArea(hs: number[]): number { const n = hs.length const l = new Array<number>(n).fill(-1), r = new Array<number>(n).fill(n) const stk = new Array<number>(n).fill(-1) let he = 0, ta = 0 for (let i = 0; i < n; i++) { while (he < ta && hs[stk[ta - 1]] > hs[i]) r[stk[--ta]] = i stk[ta++] = i } he = ta = 0 for (let i = n - 1; i >= 0; i--) { while (he < ta && hs[stk[ta - 1]] > hs[i]) l[stk[--ta]] = i stk[ta++] = i } let ans = 0 for (let i = 0; i < n; i++) { const t = hs[i], a = l[i], b = r[i] ans = Math.max(ans, (b - a - 1) * t) } return ans };`

Python 代码：

Python

复制代码

`class Solution: def largestRectangleArea(self, hs: List[int]) -> int: n, he, ta = len(hs), 0, 0 stk = [0] * n l, r = [-1] * n, [n] * n for i in range(n): while he < ta and hs[stk[ta - 1]] > hs[i]: ta -= 1 r[stk[ta]] = i stk[ta] = i ta += 1 he = ta = 0 for i in range(n - 1, -1, -1): while he < ta and hs[stk[ta - 1]] > hs[i]: ta -= 1 l[stk[ta]] = i stk[ta] = i ta += 1 ans = 0 for i in range(n): ans = max(ans, (r[i] - l[i] - 1) * hs[i]) return ans`

*  时间复杂度：O(n)O(n)O(n)
 *  空间复杂度：O(n)O(n)O(n)

### 最后 ###

这是我们「刷穿 LeetCode」系列文章的第 `No.84` 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：[github.com/SharingSour…][github.com_SharingSour] 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

作者：宫水三叶的刷题日记  
链接：https://juejin.cn/post/7236021778548342839

[format_png]: https://img-blog.csdnimg.cn/img_convert/0eca8c49c99e7cbe5ef9a708ed524d9a.webp?x-oss-process=image/format,png
[format_png 1]: https://img-blog.csdnimg.cn/img_convert/0fc7f3f388fe8802955839093c911f94.webp?x-oss-process=image/format,png
[github.com_SharingSour]: https://link.juejin.cn?target=https%3A%2F%2Fgithub.com%2FSharingSource%2FLogicStack-LeetCode