力扣LeetCode 84题：柱状图中最大的图形（暴力&单调栈详解）

约定不等于承诺〃 2023-02-14 02:37 27阅读 0赞

题目：

> 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1。  
> 求在该柱状图中，能够勾勒出来的矩形的最大面积。  
> ![在这里插入图片描述][20200531140245858.png]  
> 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 \[2,1,5,6,2,3\]。  
> ![20200531141125427.png][]
> 
> 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
> 
> 示例:  
> 输入: \[2,1,5,6,2,3\]  
> 输出: 10

### 一、暴力法 ###

##### 矩形面积 = 宽 \* 高。 #####

矩形的宽是不一定的，但是矩形的高是可以固定的。因为给定的数组里的值，就是这个矩形可能的，所有的高。

因此第一个想法是，遍历数组，对于每一个高，去计算对应的最大的宽，这样会得到一个保存了各种对应面积的新数组，最后输出数组的最大值即可。

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            if(heights.length==0){
        
                return 0;
            }
           
            int[] square=new int[heights.length];
    
            //高度取值有限，对于每一个高度，找出对应的最大宽
            for(int i=0;i<heights.length;i++){
        
                square[i]=heights[i]*getMaxWidth(heights[i],heights);
            }
            //输出最大面积
            Arrays.sort(square);
            return square[square.length-1];
        }
    
        /**
         * 根据当前高度，找出在数组中能对应的最大宽度  
         */
        public int getMaxWidth(int height, int[] heights){
        
            int width=0;
            int maxWidth=0;
            for(int i=0;i<heights.length;i++){
        
                if(heights[i]>=height){
        
                    width++;
                    maxWidth=Math.max(maxWidth,width);
                }else{
        
                    width=0;
                }
            }
            return maxWidth;
        }
    }

仔细想一想，在上面暴力方法里，求一个 **高度** 对应的 **“最大宽度”** 这件事其实是有重复的，比如在例子里两个高度为 2 的柱子，算出的最大宽度是一样的。

![20200531141631361.png][]  
两个高度为 2 的柱子，计算面积的时候其实都是用了同一个矩形。

虽然这种算最大宽的方法并不会影响结果，但是时间比较不乐观。

那么，对于每一个柱子，换成直观计算最大宽，要怎么做呢？  
从他的位置开始向左右扩散，遇到高度小于他的柱子停止。  
这样子，对于两个高度为2的柱子，对应画出的矩形也不会重复了

![在这里插入图片描述][20200531141901169.png]![在这里插入图片描述][20200531141912854.png]

修改上面第一版暴力代码里的getMaxWidth方法体，得到暴力的第二种方法：

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            if(heights.length==0){
        
                return 0;
            }
            
            int[] square=new int[heights.length];
            //高度取值有限，对于每一个柱子，找出对应的最大矩形
            for(int i=0;i<heights.length;i++){
        
                square[i]=heights[i]*getMaxWidth(i,heights);
            }
            //输出最大面积
            Arrays.sort(square);
            return square[square.length-1];
        }
    
        /**
         * 根据当前柱子，找出在数组中能画出的最宽宽度矩形  
         */
        public int getMaxWidth(int i, int[] heights){
        
            int j=i;//保存柱子位置
            int height=heights[i];//保存高度
            int maxWidth=1;
            //最左
            while(--j>=0 && heights[j]>=height){
        
                maxWidth++;
            }
            //重新最右
            j=i;
            while(++j<heights.length && heights[j]>=height){
        
                maxWidth++;
            }
            return maxWidth;
        }
    }

### 二、单调栈 ###

##### 首先，回答一个问题：什么是单调栈。 #####

栈，我们都知道；单调栈，指的就是这个栈要满足一定的单调性，比如一定要从小到大，或者从大到小。

##### 接着我们来看怎么在这个题目里利用它。 #####

在上一种暴力方法里，我们对于每一根柱子，寻找可能组成最大矩形的左右边界，都进行了向左向右扩散的过程，这个扩散过程时间复杂度是O(n)的。

利用单调栈，就能做到O(1)的复杂度，怎么想到这种方法，**我反正是想不到**，希望以后看到类似的题目，能想到吧。

先来模拟一下这个过程，采用单调递增（后者大于等于前者）的栈，存储对应柱子的下标。  
为了比较单调性的入口容易，我们假设在 heights\[ \] 数组里最开始和最后都有一个 0 元素。那么初始数组就如下图所示，绿色为数组的下标 i ：

![在这里插入图片描述][20200531142534554.png]

1.  i=0，heights\[0\]=0，虽然是人工加的，入栈。  
    ![在这里插入图片描述][2020053114352854.png]
2.  i=1，heights\[1\]=2，满足单调递增（不小于栈顶元素对应的高度），入栈；  
    ![在这里插入图片描述][2020053114354928.png]
3.  i=2，heights\[2\]=1，不满足单调递增，因为1 < 栈顶的 1 对应的heights\[1\]=2。 那此时就可以出栈  
    ![在这里插入图片描述][20200531143605499.png]  
    对于出来的这个柱子 heights\[1\]=2 来说，找到了自己的左右范围：
    
    > 左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；  
    > 右，即是当前遍历到的 i = 2 ，这显然。
    
    计算面积：高是heights\[1\]=2，宽是左右的下标之差 2-0 再 -1； area = 2 \* (2-0-1) =2
4.  继续i=2，heights\[2\]=1，现在满足单调递增了，入栈。  
    ![在这里插入图片描述][20200531143921189.png]
5.  i=3，heights\[3\]=5，满足单调递增，入栈。  
    ![在这里插入图片描述][20200531143936327.png]
6.  i=4，heights\[4\]=6，满足单调递增，入栈。  
    ![在这里插入图片描述][20200531144122950.png]
7.  i=5，heights\[5\]=2，不满足单调递增了。此时开始出栈。  
    ![在这里插入图片描述][20200531144514712.png]  
    对于出来的这个柱子 heights\[4\]=6 来说，找到了自己的左右范围：
    
    > 左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；  
    > 右，即是当前遍历到的 i = 5 ，这显然。
    
    计算面积：高是heights\[4\]=6，宽是左右的下标之差 5-3 再 -1； area = 6\* (5-3-1) =6.
8.  还是i=5，heights\[5\]=2，还是不满足，继续出栈。  
    ![在这里插入图片描述][20200531144855772.png]
    
    对于出来的这个柱子 heights\[3\]=5 来说，找到了自己的左右范围：
    
    > 左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；  
    > 右，即是当前遍历到的 i = 5 ，这显然。
    
    计算面积：高是heights\[3\]=5，宽是左右的下标之差 5-2 再 -1； area = 5\* (5-2-1) =10.
    
    （看到了吗，这里栈中记录了前一个比他小的，而当前遍历的i=5是后一个比他小的，下标之差仍然计算出了组成矩形的完整性，因为刚才出栈的i=4对应的柱子一定是高于，或者等于他的,对应的图也就是）  
    ![在这里插入图片描述][20200531144943867.png]
9.  还是i=5，heights\[5\]=2，满足递增，入栈。  
    ![在这里插入图片描述][20200531145006739.png]
10. i=6，heights\[6\]=3，满足递增，入栈。  
    ![在这里插入图片描述][20200531145024946.png]
11. .i=7，heights\[7\]=0，不满足单调递增了。此时开始出栈。  
    ![在这里插入图片描述][20200531145119980.png]  
    对于出来的这个柱子 heights\[6\]=3 来说，找到了自己的左右范围：
    
    > 左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；  
    > 右，即是当前遍历到的 i = 7 ，这显然。
    
    计算面积：高是heights\[6\]=3，宽是左右的下标之差 7-5 再 -1； area = 3\* (7-5-1) =3.
12. 仍然i=7，heights\[7\]=0，还是不满足，开始出栈。  
    ![在这里插入图片描述][20200531145212233.png]  
    对于出来的这个柱子heights\[5\]=2来说，找到了自己的左右范围：
    
    > 左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；  
    > 右，即是当前遍历到的i=7，这显然。
    
    计算面积：高是heights\[5\]=2，宽是左右的下标之差 7-2 再 -1； area = 2\*(7-2-1)=8.(这里可以再体会一下对应的矩形)
13. 仍然i=7，heights\[7\]=0，不满足递增，出栈。  
    ![在这里插入图片描述][20200531145309866.png]  
    对于出来的这个柱子heights\[2\]=1来说，找到了自己的左右范围：
    
    > 左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；  
    > 右即是当前遍历到的i=7，这显然。
    
    计算面积：高是heights\[2\]=1，宽是左右的下标之差 7-0 再 -1； area = 1\*(7-0-1)=6.
14. 还是i=7，heights\[7\]=0,满足递增（此时栈里剩一个0位置，对应高度是0），入栈。  
    ![在这里插入图片描述][2020053114540046.png]
15. i=8，对应的heights数组已经没有元素了，结束。

##### 虽然很啰嗦，但是已经了解了整个的处理流程，而且对于单调栈在这个问题里的优越性，有了理解，那就是在对于一个柱子找寻左右边界时，时间复杂度是O（1）的。 #####

接下来我们就可写出代码。从模拟的过程中可以总结出几个要点：

1.  入栈条件，满足当前的heights[i] >=栈顶heights[ stack.peek() ]；
    	2.  出栈条件，栈为空，或者不满足入栈条件。（且对于当前的一个heights[i]，不满足就要一直出）；
    	3.  结束标志，遍历完整个heights数组。
    	4.  每次保存的area，只要持续更新最大值即可。

class Solution {
        
        public int largestRectangleArea(int[] heights) {
        
            if(heights.length==0){
        
                return 0;
            }
            
            //加入两个高度为0的柱子
            int[] temp=new int[heights.length+2];
            for(int i=0;i<heights.length;i++){
        
                temp[i+1]=heights[i];
            }
            Deque<Integer> stack=new ArrayDeque<>();
            
            int area=0;
            //开始遍历
            for(int i=0;i<temp.length;i++){
        
                //如果不满足递增了，则需要出栈并计算面积
                while(!stack.isEmpty() && temp[i]<temp[stack.peek()]){
        
                    int height=temp[stack.pop()];
                    int wid=i-stack.peek()-1;//左右边界找到宽度
                    
                    area=Math.max(area , height*wid);//更新面积
                }
    
                stack.push(i);
            }
    
            return area;
        }
    }

[20200531140245858.png]: https://img-blog.csdnimg.cn/20200531140245858.png
[20200531141125427.png]: https://img-blog.csdnimg.cn/20200531141125427.png
[20200531141631361.png]: https://img-blog.csdnimg.cn/20200531141631361.png
[20200531141901169.png]: https://img-blog.csdnimg.cn/20200531141901169.png
[20200531141912854.png]: https://img-blog.csdnimg.cn/20200531141912854.png
[20200531142534554.png]: https://img-blog.csdnimg.cn/20200531142534554.png
[2020053114352854.png]: https://img-blog.csdnimg.cn/2020053114352854.png
[2020053114354928.png]: https://img-blog.csdnimg.cn/2020053114354928.png
[20200531143605499.png]: https://img-blog.csdnimg.cn/20200531143605499.png
[20200531143921189.png]: https://img-blog.csdnimg.cn/20200531143921189.png
[20200531143936327.png]: https://img-blog.csdnimg.cn/20200531143936327.png
[20200531144122950.png]: https://img-blog.csdnimg.cn/20200531144122950.png
[20200531144514712.png]: https://img-blog.csdnimg.cn/20200531144514712.png
[20200531144855772.png]: https://img-blog.csdnimg.cn/20200531144855772.png
[20200531144943867.png]: https://img-blog.csdnimg.cn/20200531144943867.png
[20200531145006739.png]: https://img-blog.csdnimg.cn/20200531145006739.png
[20200531145024946.png]: https://img-blog.csdnimg.cn/20200531145024946.png
[20200531145119980.png]: https://img-blog.csdnimg.cn/20200531145119980.png
[20200531145212233.png]: https://img-blog.csdnimg.cn/20200531145212233.png
[20200531145309866.png]: https://img-blog.csdnimg.cn/20200531145309866.png
[2020053114540046.png]: https://img-blog.csdnimg.cn/2020053114540046.png