解法转自:http://codeganker.blogspot.com/2014/04/maximal-rectangle-leetcode.html
"这道题的解法灵感来自于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 class Solution { 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[] height = new int[n];//对每一列构造数组 int max = 0; 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(helper(height), max);//从上至下每层 } return max; } public int helper(int[] height) { Stack<Integer> stack = new Stack<Integer>(); int max = 0; for (int i = 0; i <= height.length; i++) { int h; if (i == height.length) {// fake一个最终高度为1的直放 h = 0; } else { h = height[i];//当前高度 } while (!stack.isEmpty()) { if (h < height[stack.peek()]) { int indx = stack.pop(); int k = i;//计算直方的底用于求面积 if (!stack.isEmpty()) { k = i - stack.peek() - 1; } max = Math.max(max, k*height[indx]); } else { break; } } stack.push(i); } return max; } }
