84. 柱状图中最大的矩形 (opens new window)

1.一刷+单调栈

主要思路：枚举每一个节点作为树高，然后找到该节点的左右边界作为矩形的宽，计算矩形面积。因此需要找到当前柱子左右两侧小于其高度的最近的边界柱子。(这里不推荐使用起始点的思路枚举每一个可能勾勒的矩形柱子，因为枚举过程中需要记录当前的最小树高)

使用单调栈找到当前当前节点的左右边界柱子值，一般只要涉及一个节点跨越中间与另一个节点的大小关系，都可以尝试使用单调栈。具体来说，每个节点入栈之前经过出栈操作后，栈顶元素即为当前节点的边界，然后当前元素入栈。另外需要开辟数组空间来保存每个位置的边界值。

原理：核心问题在于，当前出栈的元素是否有可能成为后续入栈节点的边界？实际上并不会出现丢失边界节点的问题，原因在于出栈的元素比栈顶元素大，因此如果出栈元素能够作为当前节点的下边界，那么这个下边界并不精确，☀️显然栈顶元素才是真正的下边界(即靠近又更小)。以XXXAXXXBXXC为例子，B<A首先A出栈，然后B进栈，如果A是C的边界，那么必然存在B<A<C，因此A不符合边界条件。

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> left=new Stack<>();
        Stack<Integer> right=new Stack<>();
        int[] rightedg=new int[heights.length];
        int[] leftedg=new int[heights.length];
        left.push(-1);
        right.push(heights.length);
        int ans=0,len=heights.length-1;
        for(int i=0;i<heights.length;i++){
            while(left.peek()!=-1&&heights[i]<=heights[left.peek()]) left.pop();
            while(right.peek()!=heights.length&&heights[len-i]<=heights[right.peek()]) right.pop();
            leftedg[i]=left.peek();
            left.push(i);
            rightedg[len-i]=right.peek();
            right.push(len-i);
        }

        for(int i=0;i<heights.length;i++){
            int temp=heights[i]*(rightedg[i]-leftedg[i]-1);
            ans=Math.max(ans,temp);
        }
        return ans;
    }
}

2.二刷

💣💣解题的正确思路是枚举高度！！而不是枚举每个所有矩形的左右端点。虽然从暴力上面来看两种方法在时间复杂度上面并没有区别，但是后者需要计算n平方次矩形面积，而前置只需要计算n次面积。后者在所有可能的矩形面积上并无可优化的地方。(宽度一直在增加的同时，高度变大变小都有可能成为最大值)

✨根据高度，找到左右边第一个大于/小于当前位置的元素，可以使用单调栈。

class Solution {
    public int largestRectangleArea(int[] heights) {
        int[] right=new int[heights.length];
        int[] left=new int[heights.length];
        Stack<Integer> stack=new Stack<>();
        for(int i=0;i<heights.length;i++){
            while(stack.size()>0&&heights[stack.peek()]>heights[i]){
                int poll=stack.pop();
                right[poll]=i;
            }
            stack.push(i);
        }
        while(stack.size()>0) right[stack.pop()]=heights.length;
        for(int i=heights.length-1;i>=0;i--){
            while(stack.size()>0&&heights[stack.peek()]>heights[i]){
                int poll=stack.pop();
                left[poll]=i;
            }
            stack.push(i);
        }
        while(stack.size()>0) left[stack.pop()]=-1;

        int res=0;
        for(int i=0;i<heights.length;i++){
            res=Math.max(res,heights[i]*(right[i]-left[i]-1));
        }
        return res;
    }
}