题目：
给定一个无序矩阵，只包含0 和1 两种元素，求只包含1的最大子矩阵的大小。
[leetcode85]https://leetcode.com/problems/maximal-rectangle/
思路：
有了求解直方图最大矩形的[算法原型]//www.greatytc.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;
}
}
