题目描述
首先，可以使用暴力破解法，以每一个数字作为高度，随后遍历找出长度，最后进行大小的匹配即可，但是由于是O(n^2)复杂度，肯定过不了LeetCode的OJ，随后参照网上的过程进行优化处理。
对于任意一个bar n，我们得到的包含该bar n的矩形区域里面bar n是最小的。我们使用ln和rn来表示bar n向左以及向右第一个小于bar n的bar的索引位置。
譬如题目中的bar 2的高度为5，它的ln为1，rn为4。包含bar 2的矩形区域面积为(4 - 1 - 1) * 5 = 10。
我们可以从左到右遍历所有bar，并将其push到一个stack中，如果当前bar的高度小于栈顶bar，我们pop出栈顶的bar，同时以该bar计算矩形面积。那么我们如何知道该bar的ln和rn呢？rn铁定就是当前遍历到的bar的索引，而ln则是当前的栈顶bar的索引，因为此时栈顶bar的高度一定小于pop出来的bar的高度。
为了更好的处理最后一个bar的情况，我们在实际中会插入一个高度为0的bar，这样就能pop出最后一个bar并计算了。
个人理解就是使用栈进行数据的存储，对数组进行遍历的过程中，由于栈顶元素一定比下面的元素大，遍历过程中找到当前元素在栈中对应的位置，即可限定范围，缩小范围之后进行查找即可完成优化，具体解决代码如下：
public class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int[] numbers = new int[heights.length + 1];
for (int i = 0; i < heights.length; i++) {
numbers[i] = heights[i];
}
numbers[heights.length] = 0;
int sum = 0, i = 0;
while (i < numbers.length) {
if (stack.isEmpty() || numbers[i] > numbers[stack.peek()]) {
stack.add(i);
i++;
} else {
int t = stack.peek();
stack.pop();
sum = Math.max(sum, numbers[t] * (stack.isEmpty() ? i : i - stack.peek() - 1));
}
}
return sum;
}
}
