LeetCode柱状图中最大的矩形

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

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

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3] 输出: 10

来源：力扣（LeetCode）链接：leetcode-cn.com/problems/la…

解题思路

１. 循环2次，获取高度最小的值乘以相间隔的距离得出面积。用Math.max方法，找出最大值。效率太低了。

public int largestRectangleArea(int[] heights) {
    int max = Integer.MAX_VALUE;
    int area = 0;
    for (int i = 0; i < heights.length ; i++) {
        for (int j = i; j < heights.length; j++) {
            max = Math.min(max, heights[j]);
            area = Math.max(area, max * (j-i+1));
        }
    }
    return area;
}

使用栈的方法

定义栈，加入初始值-1.
循环数组，判断栈中的元素不等于初始值，并且通过栈中的下标找到的值大于当前的值，就将数据出栈，使用heights[栈中取出的最后入栈的值的下标] 乘以当前循环次i减去栈中倒数第二个下标在减一。算出最大的面积。

public int largestRectangleArea(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int max = 0;
    for (int i = 0; i < heights.length; i++) {
        while(stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
            max = Math.max(max, heights[stack.pop()] * (i - stack.peek() - 1));
        }
        stack.push(i);
    }
    while(stack.peek() != -1) {
        max = Math.max(max, heights[stack.pop()] * (heights.length - stack.peek() - 1));
    }
    return max;
}