84. 柱状图中最大的矩形（高频题）

84. 柱状图中最大的矩形

• 解题思路
• 代码

解题思路

一刷 2021/3/17，没搞懂
题解见这里

二刷：2021/4/6
这题其实就是说：
我们可以遍历每根柱子，以当前柱子 i 的高度作为矩形的高，那么矩形的宽度边界即为向左找到第一个高度小于当前柱体 i 的柱体，向右找到第一个高度小于当前柱体 i 的柱体。

然后我们可以利用单调递增栈，这样的话：假如元素i，要入栈，但是栈顶元素大于要入栈得元素，那么，即将入栈得元素就是栈顶元素得 右边界，栈顶元素下面那个元素就是栈顶元素得左边界，再以栈顶元素为高，计算出面积即可！

注意最后求出来是以栈顶元素为高 的矩形面积哦！

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        // 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
        int[] tmp = new int[heights.length + 2];
        System.arraycopy(heights, 0, tmp, 1, heights.length); 
        
        Stack<Integer> stack = new Stack<>();

        int area = 0;
        for (int i = 0; i < tmp.length; i++) {
            // 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
            // 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
            // 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积🌶️ ～
            while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
                int h = tmp[stack.pop()];
                area = Math.max(area, (i - stack.peek() - 1) * h);   
            }
            stack.push(i);
        }

        return area;
    }
}