84.柱状图中最大的矩形.md

84.柱状图中最大的矩形

题目

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

例如:height = [4,3,2,5,6].
则柱状图中每一竖列的高分别为4，3，2，5，6。
能找到的最大矩形即为以5为底，以2为高的矩形。面积为10.

方法（单调栈）

依次计算以每一竖列为高的所有矩形中最大的面积。即统计从一个竖列向左右扩，左边和右边分别能扩多远（如果在左右遇到了低于它的竖列，则无法扩）。

我们维护一个单调栈结构来做到这一点（由栈底到栈顶，元素大小从小到大），准备一个栈。先将第一个元素入栈。之后尝试将数组中的每一个元素入栈。

• 如果要加入的元素小于栈顶元素，那么为了维护栈的单调性，将栈顶依次弹出，直到栈顶元素小于要加入元素了，将元素入栈。对于弹出的每个元素，都代表着直方图中的每一个竖列。弹出时进行结算，此单调栈的原则是：谁让它弹出，谁就是它右边最近比它小的。而它在栈中下面的那个元素代表着它左边最近比它小的。因此，知道它左右两边最近比它小的，就可以知道以它为竖列的最大矩形面积。
• 如果要加入的元素大于栈顶元素，符合栈的单调性，直接入栈。

当遍历完数组中的所有元素后，如果栈非空，将栈中元素弹空。每弹出一个元素，对它进行结算。计算以它为竖列的最大矩形面积。对于这些元素，因为没有元素使得它弹出，因此它没有右边比它小的元素，它可以扩到直方图的最右边。

代码

public static int maxRecFromBottom(int[] height){
    if(height == null || height.length == 0)
        return 0;
    int maxArea = 0;
    Stack<Integer> stack = new Stack<>();
    for(int i = 0; i < height.length; i++){
        //如果要加入的元素小于栈顶元素，将栈顶依次弹出。弹出时进行结算
        while(!stack.isEmpty() && height[i] <=height[stack.peek()]){
            int j = stack.pop();
            //k是以j为竖列能扩到的左边界。即它在栈中下面的那个元素。
            //如果j弹出时，它下面没元素，那么左边界为-1.否则，它的左边界为它下面那个元素在数组中的下标。
            int k = stack.isEmpty() ? -1 : stack.peek();
            //遍历到i位置令j弹出，因此i为以j为竖列能扩到的右边界。
            //所以以j为竖列能扩出的最大矩形：底为i - k - 1。高为height[j]
            int curArea = (i - k - 1) * height[j];
            maxArea = Math.max(maxArea, curArea);
        }
        //否则，直接将元素入栈。
        stack.push(i);
    }
    //在对数组遍历完后，对于栈中剩余的那些元素，不要忘记结算。
    //因为没有元素令它们弹出，所以它们在右边没有比它们小的元素。向右可以扩到头height.length
    while (!stack.isEmpty()){
        int j = stack.pop();
        int k = stack.isEmpty() ? -1 : stack.peek();
        int curArea = (height.length - k - 1) * height[j];
        maxArea = Math.max(maxArea, curArea);
    }
    return maxArea;
}