原题链接: http://oj.leetcode.com/problems/maximal-rectangle/
这是一道很综合的题目，要求在0-1矩阵中找出面积最大的全1矩阵。
这道题的解法灵感来自于Largest Rectangle in Histogram这道题。假设我们把矩阵沿着某一行切下来。然后把切的行作为底面。将自底面往上的矩阵看成一个直方图（histogram）。
算法的基本思路已经出来了，剩下的就是一些节省时间空间的问题了。
我们怎样计算某一行为底面时直方图的高度呢？ 假设又一次计算。那么每次须要的计算数量就是当前行数乘以列数。然而在这里我们会发现一些动态规划的踪迹，假设我们知道上一行直方图的高度，我们仅仅须要看新加进来的行（底面）上相应的列元素是不是0。假设是。则高度是0。否则则是上一行直方图的高度加1。利用历史信息。我们就能够在线行时间内完毕对高度的更新。
空间上，我们仅仅须要保存上一行直方图的高度O(n)，加上Largest Rectangle in Histogram中所使用的空间O(n)，所以总空间复杂度还是O(n)。
这是一道很综合的题目，要求在0-1矩阵中找出面积最大的全1矩阵。
刚看到这道题会比較无从下手，brute force就是对于每一个矩阵都看一下。总共同拥有m(m+1)/2*n(n+1)/2个子矩阵（原理跟字符串子串相似。字符串的子串数有n(n+1)/2，仅仅是这里是二维情形，所以是两个相乘），复杂度相当高，肯定不是面试官想要的答案。就不继续想下去了。
这道题的解法灵感来自于Largest Rectangle in Histogram这道题。假设我们把矩阵沿着某一行切下来。然后把切的行作为底面。将自底面往上的矩阵看成一个直方图（histogram）。
直方图的中每一个项的高度就是从底面行開始往上1的数量。
依据
Largest Rectangle in Histogram我们就能够求出当前行作为矩阵下边缘的一个最大矩阵。接下来假设对每一行都做一次
Largest Rectangle in Histogram。从当中选出最大的矩阵，那么它就是整个矩阵中面积最大的子矩阵。算法的基本思路已经出来了，剩下的就是一些节省时间空间的问题了。
我们怎样计算某一行为底面时直方图的高度呢？ 假设又一次计算。那么每次须要的计算数量就是当前行数乘以列数。然而在这里我们会发现一些动态规划的踪迹，假设我们知道上一行直方图的高度，我们仅仅须要看新加进来的行（底面）上相应的列元素是不是0。假设是。则高度是0。否则则是上一行直方图的高度加1。利用历史信息。我们就能够在线行时间内完毕对高度的更新。
我们知道。
Largest Rectangle in Histogram的算法复杂度是O(n)。所以完毕对一行为底边的矩阵求解复杂度是O(n+n)=O(n)。接下来对每一行都做一次。那么算法总时间复杂度是O(m*n)。
空间上，我们仅仅须要保存上一行直方图的高度O(n)，加上Largest Rectangle in Histogram中所使用的空间O(n)，所以总空间复杂度还是O(n)。
代码例如以下：
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0)
{
return 0;
}
int maxArea = 0;
int[] height = new int[matrix[0].length];
for(int i=0;i<matrix.length;i++)
{
for(int j=0;j<matrix[0].length;j++)
{
height[j] = matrix[i][j]=='0'?0:height[j]+1;
}
maxArea = Math.max(largestRectangleArea(height),maxArea);
}
return maxArea;
}
public int largestRectangleArea(int[] height) {
if(height==null || height.length==0)
{
return 0;
}
int maxArea = 0;
LinkedList<Integer> stack = new LinkedList<Integer>();
for(int i=0;i<height.length;i++)
{
while(!stack.isEmpty() && height[i]<=height[stack.peek()])
{
int index = stack.pop();
int curArea = stack.isEmpty()?i*height[index]:(i-stack.peek()-1)*height[index];
maxArea = Math.max(maxArea,curArea);
}
stack.push(i);
}
while(!stack.isEmpty())
{
int index = stack.pop();
int curArea = stack.isEmpty()?height.length*height[index]:(height.length-stack.peek()-1)*height[index];
maxArea = Math.max(maxArea,curArea);
}
return maxArea;
}