柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例

输入：heights = [2,1,5,6,2,3]

输出：10

解释：最大的矩形为图中红色区域，面积为 10

思路

这道题与接雨水非常的相似，接雨水是找凹槽，这道题是找凸起，并且对于不完整的凹槽（左边没有柱子）是不用算面积的，因为水不可能装在个破碗中，而不完整的凸起是要算面积的，为了方便计算，可以在数组两边各加一个高度为0的柱子，这样就都可以按照完整凸起来算。

因为是找凸起，所以单调栈因为是从栈底到栈顶单调递增，当将要入栈的元素小于栈顶元素时就出现了凸起。然后使用中间柱子高度乘以左右柱子之间距离就可以求出面积。

要注意的是，单调栈中只存放坐标，而单调递增是指坐标对应高度单调递增

为什么下标1的那块面积变成了10呢，注意，面积是左右柱子距离乘以中间高度，因为先出栈的柱子2的高度肯定大于后出栈的柱子1，所以实际上10表示的是如下图表示的面积：

所以示例的整个过程为：

实现代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxArea=0;
        //数组扩容，在最前和最后都加0
        int[] hArray=new int[heights.length+2];
        hArray[0]=hArray[hArray.length-1]=0;
        for(int i=0;i< heights.length;i++) {
            hArray[i+1]=heights[i];
        }
        Deque<Integer> stack=new ArrayDeque<>();
        stack.push(0);
        for(int i=1;i<hArray.length;i++) {
            while (hArray[i]<hArray[stack.peek()]) {
                int mid=stack.pop();
                int leftIndex= stack.peek();
                maxArea=Math.max((i-leftIndex-1)*hArray[mid],maxArea);
            }
            stack.push(i);
        }
        return maxArea;
    }
}