【力扣刷题】单调栈：84. 柱状图中最大的矩形

àì夳堔傛蜴生んèń 2023-09-28 11:52 55阅读 0赞

题目：

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

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

![8824e083f7b94529980f42c70b97dd83.png][]

![2e3a7bd677384c7ba4d4cf46969d0188.png][]

思路：

//单调递增栈，对于栈中的柱体来说，左边第一个高度小于自身的柱体就在自己下方

//遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的，就入栈

//否则就是找到了栈顶元素的右边的第一个小于自身的柱体，出栈栈顶元素，同时可以计算栈顶元素的对应的矩形的最大面积了

//给数组最后一个元素添加一个0，用这个条件来让栈里面所有元素都出栈

//左边特殊处理的话，如果某个栈顶元素出栈后栈为空，说明左边没有元素比它矮，它自己是最矮的，左边可以延申到0

class Solution {
        public int largestRectangleArea(int[] heights) {
            //单调递增栈，对于栈中的柱体来说，左边第一个高度小于自身的柱体就在自己下方
            //遍历每个柱体，若当前的柱体高度大于等于栈顶柱体的，就入栈
            //否则就是找到了栈顶元素的右边的第一个小于自身的柱体，出栈栈顶元素，同时可以计算栈顶元素的对应的矩形的最大面积了
            //给数组最后一个元素添加一个0，用这个条件来让栈里面所有元素都出栈
            //左边特殊处理的话，如果某个栈顶元素出栈后栈为空，说明左边没有元素比它矮，它自己是最矮的，左边可以延申到0
            int[] newH = new int[heights.length + 1];
            for(int i = 0; i < heights.length;i++){
                newH[i] = heights[i];
            }
            newH[heights.length] = 0;
            Stack<Integer> stack = new Stack<>();
            int res = 0;
            for(int i = 0;i < heights.length + 1;i++){
                while(stack.size() != 0 && newH[stack.peek()] > newH[i]){
                    res = Math.max(res,newH[stack.pop()] * (stack.size() == 0 ? i : (i - stack.peek() - 1))); 
                }
                stack.push(i);
            }
            return res;
        }
    }

[8824e083f7b94529980f42c70b97dd83.png]: https://img-blog.csdnimg.cn/8824e083f7b94529980f42c70b97dd83.png
[2e3a7bd677384c7ba4d4cf46969d0188.png]: https://img-blog.csdnimg.cn/2e3a7bd677384c7ba4d4cf46969d0188.png