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

import java.util.PriorityQueue;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param heights int整型一维数组
     * @return int整型
     */

    //总体思想是遍历数组 每次都向左右两边扩散
    public int largestRectangleArea(int[] heights) {
        //创建一个大顶堆 用来存放每次的面积 程序结束返回第一个值就是最大的面积
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
        //返回特殊情况
        if (heights.length == 0) {
            return 0;
        }
        //返回特殊情况
        if (heights.length == 1) {
            return heights[0];
        }

        //遍历数组
        for (int i = 1; i < heights.length; i++) {
            //给每一次遍历 赋一个初始的宽度
            int wit = 1;
            //向左边扩算
            for (int l = i - 1; l >= 0; l--) {
                //拼接成矩形需要扩算方向的柱子高度大于等于当前的高度
                if (heights[l] != 0 && heights[l] >= heights[i]) {
                    wit++;
                } else {
                    //不满足条件就跳出向左边的扩算
                    break;
                }

            }
            //向右边扩算
            for (int r = i + 1; r <= heights.length - 1; r++) {

                //拼接成矩形需要扩算方向的柱子高度大于等于当前的高度
                if (heights[r] != 0 && heights[r] >= heights[i]) {
                    wit++;
                } else {
                    //不满足条件就跳出向右边的扩算
                    break;
                }

            }
            //计算矩形面积并且存进大顶堆
            pq.offer(wit * heights[i]);

        }
        //返回大顶堆的head
        return pq.poll();
    }
}