题解 | #直方图内最大矩形#

题意整理

给定一个数组heights，长度为n，height[i]是在第i点的高度。
每个height都表示一个直方图，宽度为1。求能组成的最大面积的矩形。

方法一（枚举）

1.解题思路

思路很简单，就是遍历每一个直方图，将其高度作为矩形的高度，然后分别向前、向后延申，得到可能的矩形的最大长度。计算每一个矩形的面积，取最大值即可。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        //总宽度
        int n=heights.length;
        int res=0;
        for(int i=0;i<n;i++){
            int start=-1;
            //从后往前找到第一个小于当前的高度，记为start
            for(int j=i-1;j>=0;j--){
                if(heights[j]<heights[i]){
                    start=j;
                    break;
                }
            }
            int end=n;
            //从前往后找到第一个小于当前的高度，记为end
            for(int j=i+1;j<n;j++){
                if(heights[j]<heights[i]){
                    end=j;
                    break;
                }
            }
            //根据start、end得到以当前高度为高的最大矩形面积，取所有可能的最大值
            res=Math.max(res,(end-start-1)*heights[i]);
        }        
        return res;
    }
}

3.复杂度分析

时间复杂度：两层循环，最坏情况下所有元素相等，内层循环每次都要遍历 $n - 1$ 次，总共需要遍历 $n * (n - 1)$ 次，所以时间复杂度是 $O (n^{2})$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度为 $O (1)$ 。

方法二（单调栈）

1.解题思路

新建单调栈，通过单调栈维护一个单调不递减的序列的下标。
只要栈顶元素比当前大，则可以统计以栈顶元素为高的最大面积。由于单调栈内元素是单调不递减的，可以确定矩形右边界为当前元素前一位，而左边界为弹栈后栈顶元素后一位。如果栈中元素为空，说明0为左边界，因为单调不递减，后面的肯定比它大，前面的比他小，而为空，说明已经没有比它小的了，之前弹出的元素也一定比它大，所以左边界要从0开始。
如果遍历完之后，单调栈还不为空，则以同样的方式继续统计可能的最大面积。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param heights int整型一维数组 
     * @return int整型
     */
    public int largestRectangleArea (int[] heights) {
        //总宽度
        int n=heights.length;
        //新建单调栈
        ArrayDeque<Integer> stack=new ArrayDeque<>();
        
        int res=0;
        for(int i=0;i<n;i++){
            //只要栈顶元素比当前大，则可以统计以栈顶元素为高的最大面积
            while(!stack.isEmpty()&&heights[stack.peek()]>heights[i]){
                //由于单调栈内元素是单调不递减的，L到i-1之间的高度一定大于等于curHeight
                int curHeight=heights[stack.pop()];
                //如果栈中元素为空，说明0到i-1之间的高度均大于等于curHeight
                int L=stack.isEmpty()?0:stack.peek()+1;
                res=Math.max(res,(i-L)*curHeight);
            }
            stack.push(i);
        }
        
        //如果遍历完之后，单调栈还不为空，则继续统计可能的最大面积
        while(!stack.isEmpty()){
            int curHeight=heights[stack.pop()];
            int L=stack.isEmpty()?0:stack.peek()+1;
            res=Math.max(res,(n-L)*curHeight);
        }
        
        return res;
    }
}

3.复杂度分析

时间复杂度：每个元素最多进栈和出栈一次，所以时间复杂度是 $O (n)$ 。
空间复杂度：需要额外大小为n的栈，所以空间复杂度为 $O (n)$ 。