问题描述：
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Return 6.
算法分析：
这道题可以应用之前解过的Largetst Rectangle in Histogram一题辅助解决。解决方法是：
按照每一行计算列中有1的个数，作为高度，当遇见0时，这一列高度就为0。然后对每一行计算 Largetst Rectangle in Histogram，最后得到的就是结果。
public class MaximalRectangle
{
public int maximalRectangle(char[][] matrix)
{
if(matrix.length == 0 || matrix[0].length == 0 || matrix == null)
{
return 0;
}
int m = matrix.length;
int n = matrix[0].length;
int max = 0;
int[] height = new int[n];
for(int i = 0; i < m; i ++)
{
for(int j = 0; j < n; j ++)
{
if(matrix[i][j] == '0')
{
height[j] = 0;
}
else
{
height[j] += 1;
}
}
max = Math.max(max, largestRectangleArea2(height));
}
return max;
}
public int largestRectangleArea2(int[] heights)
{
Stack<Integer> stack = new Stack<>();
int[] h = Arrays.copyOf(heights, heights.length + 1);//h最后元素补0，为了让所有元素出栈，所以补0
int i = 0;
int maxArea = 0;
while(i < h.length)
{
if(stack.isEmpty() || h[stack.peek()] <= h[i])
{
stack.push(i++);//只存放单调递增的索引
}
else
{
int t = stack.pop();//stack.isEmpty说明i是栈里最小的元素，面积为i*h[t]
maxArea = Math.max(maxArea, h[t]*(stack.isEmpty() ? i : i-stack.peek()-1));
}
}
return maxArea;
}
}