给了一个数组，数组值代表高度，这构成了一个直方图，求直方图中最大矩形的面积

[leetcode84]https://leetcode.com/problems/largest-rectangle-in-histogram/

思路：

考虑必须包含某个柱子的矩形的最大面积，那么我们就需要找到这个柱子往左和往右的边界，这样宽度高度都有了，就有了必须包含这个柱子的最大面积，左右柱子的这个最大面积求出来，这其中的最大即为全局最大。

算法步骤

1. 使用一个stack，首先压入第一个元素的位置，然后遍历数组，在遇到当前数组大于栈顶对应值时，直接入栈即可，否则进行出栈操作，知道栈顶元素的值小于当前元素。这一过程中即可求出必须包含栈顶元素的最大矩阵面积。
   然后压入当前元素。
2. 遍历结束后如果栈中还有元素，也需要将其弹出，并计算。

算法原理

假设现在遍历到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;
    }
}