[LeetCode] 84. Largest Rectangle in Histogram

Given an array of integers heights representing the histogram’s bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:
1 <= heights.length <= 105
0 <= heights[i] <= 104

柱状图中最大的矩形。

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

思路

题意是给一个数组表示一些非负整数，代表一些 bars，请你返回由这些 bar 组成的最大矩形的面积。

思路是单调栈。这个题可以用别的方法，但是复杂度都不如单调栈的思路。关于这个题本身，我参考了这个帖子，他讲的非常好，起码帮助我理解了这道题单调栈的做法。至于代码，你只要看懂这个帖子的讲解，代码一定看得懂。唯一需要注意的是为什么 for loop 要遍历完 input 数组之后再多走一步，是为了让遍历完 input 之后有一个机会停下来结算由最后一个 bar 组成的矩形的最大面积，否则如果是一直递增的 bars，遍历完是没有机会停下来结算的。

这个题为什么可以用单调栈做，并且单调栈的思想适用于什么样的题目，我觉得是比如你在一堆单调增或者单调减的数据里面突然找一个拐点，就可以尝试利用单调栈。这个还是需要多做才有感觉。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        int res = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i <= n; i++) {
            int h = i == n ? 0 : heights[i];
            while (!stack.isEmpty() && h < heights[stack.peekLast()]) {
                int height = heights[stack.pollLast()];
                int start = stack.isEmpty() ? -1 : stack.peekLast();
                int area = height * (i - start - 1);
                res = Math.max(res, area);
            }
            stack.offerLast(i);
        }
        return res;
    }
}

JavaScript实现

/**
 * @param {number[]} heights
 * @return {number}
 */
var largestRectangleArea = function(heights) {
    // corner case
    if (heights == null || heights.length == 0) {
        return 0;
    }

    // normal case
    let stack = [];
    let res = 0;
    for (let i = 0; i <= heights.length; i++) {
        let h = i == heights.length ? 0 : heights[i];
        while (stack.length && h < heights[stack[stack.length - 1]]) {
            let height = heights[stack.pop()];
            let start = !stack.length ? -1 : stack[stack.length - 1];
            let area = height * (i - start - 1);
            res = Math.max(res, area);
        }
        stack.push(i);
    }
    return res;
};

其他思路

暴力解，O(n^2)，OA也勉强能过，不会超时
Java实现

class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int area = 0;
        // 枚举左边界
        for (int left = 0; left < len; left++) {
            int minHeight = Integer.MAX_VALUE;
            // 枚举右边界
            for (int right = left; right < len; right++) {
                // 确定高度，我们要最小的高度
                minHeight = Math.min(minHeight, heights[right]);
                // 计算面积，我们要保留计算过的最大的面积
                area = Math.max(area, (right - left + 1) * minHeight);
            }
        }
        return area;
    }
}

相关题目

84. Largest Rectangle in Histogram
85. Maximal Rectangle
221. Maximal Square
1277. Count Square Submatrices with All Ones
1727. Largest Submatrix With Rearrangements