题目：

给定一个无序矩阵，只包含0 和1 两种元素，求只包含1的最大子矩阵的大小。
[leetcode85]https://leetcode.com/problems/maximal-rectangle/

思路：

有了求解直方图最大矩形的[算法原型]http://www.jianshu.com/p/b871972747c0 之后，这个问题就方便许多。
可以考虑必须以某一行为底的最大1子矩阵，这样所有行为底的最大即为所求。

算法步骤

注意以求解某行为底怎么求。用一个数组h来作为辅助数组.h[i]为这行的第i列往上有多少个连续的1,如果这行的i位置为0,则h[i]=0,否则h[i]=h[i]+1。

public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if(matrix==null||matrix.length==0||matrix[0].length==0)
            return 0;
        int res=0;
        int[] h=new int[matrix[0].length];
        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                h[j]=matrix[i][j]=='0'?0:h[j]+1;
            }
            res=Math.max(res,largestRectangleArea(h));
        }
        return res;
    }
     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;
    }
}