84. 柱状图中最大的矩形 : 单调栈经典运用题

我报名参加金石计划一期挑战——瓜分10万奖池，这是我的第28篇文章，点击查看活动详情

题目描述

这是 LeetCode 上的 84. 柱状图中最大的矩形 ，难度为 中等。

Tag : 「单调栈」

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

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

示例 1:

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

示例 2：

输入： 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 代码：

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)O(n)
• 空间复杂度：O(n)O(n)O(n)

最后

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

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

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

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

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉