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

题目：

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 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 的柱子，算出的最大宽度是一样的。

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

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

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

在这里插入图片描述

修改上面第一版暴力代码里的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 ：

在这里插入图片描述

i=0，heights[0]=0，虽然是人工加的，入栈。
i=1，heights[1]=2，满足单调递增（不小于栈顶元素对应的高度），入栈；
i=2，heights[2]=1，不满足单调递增，因为1 < 栈顶的 1 对应的heights[1]=2。那此时就可以出栈

对于出来的这个柱子 heights[1]=2 来说，找到了自己的左右范围：

左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；
右，即是当前遍历到的 i = 2 ，这显然。

计算面积：高是heights[1]=2，宽是左右的下标之差 2-0 再 -1； area = 2 * (2-0-1) =2
继续i=2，heights[2]=1，现在满足单调递增了，入栈。
i=3，heights[3]=5，满足单调递增，入栈。
i=4，heights[4]=6，满足单调递增，入栈。
i=5，heights[5]=2，不满足单调递增了。此时开始出栈。

对于出来的这个柱子 heights[4]=6 来说，找到了自己的左右范围：

左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；
右，即是当前遍历到的 i = 5 ，这显然。

计算面积：高是heights[4]=6，宽是左右的下标之差 5-3 再 -1； area = 6* (5-3-1) =6.
还是i=5，heights[5]=2，还是不满足，继续出栈。

对于出来的这个柱子 heights[3]=5 来说，找到了自己的左右范围：

左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；
右，即是当前遍历到的 i = 5 ，这显然。

计算面积：高是heights[3]=5，宽是左右的下标之差 5-2 再 -1； area = 5* (5-2-1) =10.

（看到了吗，这里栈中记录了前一个比他小的，而当前遍历的i=5是后一个比他小的，下标之差仍然计算出了组成矩形的完整性，因为刚才出栈的i=4对应的柱子一定是高于，或者等于他的,对应的图也就是）
还是i=5，heights[5]=2，满足递增，入栈。
i=6，heights[6]=3，满足递增，入栈。
.i=7，heights[7]=0，不满足单调递增了。此时开始出栈。

对于出来的这个柱子 heights[6]=3 来说，找到了自己的左右范围：

左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；
右，即是当前遍历到的 i = 7 ，这显然。

计算面积：高是heights[6]=3，宽是左右的下标之差 7-5 再 -1； area = 3* (7-5-1) =3.
仍然i=7，heights[7]=0，还是不满足，开始出栈。

对于出来的这个柱子heights[5]=2来说，找到了自己的左右范围：

左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；
右，即是当前遍历到的i=7，这显然。

计算面积：高是heights[5]=2，宽是左右的下标之差 7-2 再 -1； area = 2*(7-2-1)=8.(这里可以再体会一下对应的矩形)
仍然i=7，heights[7]=0，不满足递增，出栈。

对于出来的这个柱子heights[2]=1来说，找到了自己的左右范围：

左，即是此时变化后的栈的栈顶元素，因为单调递增，左边的肯定比他小；
右即是当前遍历到的i=7，这显然。

计算面积：高是heights[2]=1，宽是左右的下标之差 7-0 再 -1； area = 1*(7-0-1)=6.
还是i=7，heights[7]=0,满足递增（此时栈里剩一个0位置，对应高度是0），入栈。
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;
    }
}