给了一个数组，数组值代表高度，这构成了一个直方图，求直方图中最大矩形的面积
[leetcode84]https://leetcode.com/problems/largest-rectangle-in-histogram/
思路：
考虑必须包含某个柱子的矩形的最大面积，那么我们就需要找到这个柱子往左和往右的边界，这样宽度高度都有了，就有了必须包含这个柱子的最大面积，左右柱子的这个最大面积求出来，这其中的最大即为全局最大。
算法步骤
- 使用一个stack，首先压入第一个元素的位置，然后遍历数组，在遇到当前数组大于栈顶对应值时，直接入栈即可，否则进行出栈操作，知道栈顶元素的值小于当前元素。这一过程中即可求出必须包含栈顶元素的最大矩阵面积。
然后压入当前元素。 - 遍历结束后如果栈中还有元素，也需要将其弹出，并计算。
算法原理
假设现在遍历到i，如果栈顶元素小于heights[i],表明这个i就是栈顶元素的左边界，而栈顶元素的右边界就是栈顶元素的下边一个元素（为空补-1）,这样就可以求得必须包含栈顶元素的最大矩形面积。这样遍历一次之后就所有的情况都考虑到了。需要注意的是你遍历结束之后，可能栈中还有元素，也需要把这些元素弹出结算，此时这些元素的右边界即为heights.length。
代码
public class Solution {
public int largestRectangleArea(int[] heights) {
if(heights==null||heights.length==0)
return 0;
int res=0;
Stack<Integer> stack=new Stack<Integer>();
for(int i=0;i<heights.length;i++){
while(!stack.isEmpty()&&heights[i]<=heights[stack.peek()]){
int cur=stack.pop();
int left=stack.isEmpty()?-1:stack.peek();
res=Math.max(res,(i-left-1)*heights[cur]);
}
stack.push(i);
}
while(!stack.isEmpty()){
int cur=stack.pop();
int left=stack.isEmpty()?-1:stack.peek();
res=Math.max(res,(heights.length-left-1)*heights[cur]);
}
return res;
}
}
