题目形容
这是 LeetCode 上的 84. 柱状图中最大的矩形 ，难度为 艰难。
Tag : 「枯燥栈」
给定 n 个非负整数，用来示意柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，可能勾画进去的矩形的最大面积。
示例 1:
输出：heights = [2,1,5,6,2,3]输入：10解释：最大的矩形为图中红色区域，面积为 10示例 2：
输出： heights = [2,4]输入： 4提醒：
- $1 <= heights.length <=10^5$
- $0 <= heights[i] <= 10^4$
枯燥栈 + 枚举高度
为了不便，咱们令 heights 为 hs。
最终矩形的高度必然取自某个 $hs[i]$，因而咱们能够枚举最终矩形的高度来做。
问题转换为当应用某个 $hs[i]$ 作为矩形高度时，该矩形所能获得的最大宽度为多少。
假如咱们可能预处理出 l 和 r 数组，其中 $l[i]$ 代表地位 $i$ 右边最近一个比其小的地位（初始值为 $-1$），$r[i]$ 代表地位 $i$ 左边最近一个比其小的地位（初始值为 $n$），那么 $r[i] - l[i] - 1$ 则是以 $hs[i]$ 作为矩形高度时所能获得的最大宽度。
预处理 l 和 r 则是经典的「求最近一个比以后值大的地位」枯燥栈问题。
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 代码：
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 代码：
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)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.84 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试/面试」相干材料可拜访排版精美的 合集新基地
本文由mdnice多平台公布