#yyds干货盘点# 名企真题专题：直方图内最大矩形

1.简述：

描述

给定一个数组heights，长度为n，height[i]是在第i点的高度，那么height[i]表示的直方图，能够形成的最大矩形是多少?

1.每个直方图宽度都为1

2.直方图都是相邻的

3.如果不能形成矩形，返回0即可

4.保证返回的结果不会超过231-1

数据范围:

如输入[3,4,7,8,1,2]，那么如下:

示例1

输入：

[3,4,7,8,1,2]

返回值：

14

示例2

输入：

[1,7,3,2,4,5,8,2,7]

返回值：

16

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;
    }
}