题目大意：给一个由0和1组成r行c列的矩阵M，找出其中面积最大的由1组成的矩形。
这道题目和之前一道提供高度计算最大矩形的题目是一样的，这里也一块说一下。这道题目提供若干宽度为1的柱形，求其中最大的矩形面积，柱形由高度和位置唯一决定，由一个数组H表示，H[i]表示编号为i的柱形的高度。
显然如果一个矩形最大，那么其必定包含一个高度最低的柱形，设其下标为i。假设矩形的左右边界矩形的下标为a+1和b-1，那么必然有H[a]<H[i]和H[b]<H[i]，否则矩形可以进一步扩大，与其最大这一前提相悖。对于每一个柱形H[i]，利用左右边界的性质可以决定唯一的最大矩形候选，而只要挑选出所有矩形候选中面积最大者，就是我们需要的结果。下面稍微说明一下如何在O(n)时间内找到每一个最大矩形候选的右边界。从0到n遍历整个H，将所有未找到右边界的柱形加入到一个栈结构中。显然栈中的柱形高度应该是递增的。每次遇到一个新的柱形，将栈中所有高度比其小的柱形全部弹出并设置右边界为新柱形，最后将新柱形加入到栈中。等到遍历结束，就将所有栈中剩余的柱形的右边界设置为n（因为剩余的都是没有匹配到右边界的）。同理可以利用类似的思路得到所有矩形候选的左边界。这两个过程的时间复杂度都是O(n)（因为每一个柱形只入栈和出栈各一次，共n个柱形）。有了左右边界计算面积就很容易了，可以在O(n)的时间复杂度内完成。
因此对于上面的这种问题我们始终能在O(n)的时间复杂度内解决。
现在说明如何解决Maximal Rectangle这道题目。首先我们可以将矩阵的第0行到第i行理解为一个柱形图，且第j列的高度为M[i][j],M[i-1][j],...,M[0][j]中只包含1的最长前缀的长度。可以通过动态规划得到第i行第j列的高度H[i][j]，因为H[i][j] = 1 == M[i][j] ? H[i-1][j] + 1 : 0。这样我们要找面积最大的只由1组成的矩形等价于找r个柱形图中最大的矩形，每个柱形图通过的方法可以在O(c)时间内计算得到，故总时间为O(rc)，加上动态规划所花费的O(rc)的时间，因此总的时间复杂度为O(rc)。
下面上代码：
1 class Solution { 2 public int maximalRectangle(char[][] matrix) 3 { 4 if(matrix.length == 0 || matrix[0].length == 0) 5 { 6 return 0; 7 } 8 int h = matrix.length; 9 int w = matrix[0].length;10 int[] heights = new int[w];11 int max = 0;12 for(int i = 0; i < h; i++)13 {14 char[] row = matrix[i];15 for(int j = 0; j < w; j++)16 {17 heights[j] = row[j] == '0' ? 0 : heights[j] + 1;18 }19 max = Math.max(max, theLargestArea(heights));20 }21 return max;22 }23 24 public int theLargestArea(int[] heights)25 { 26 int n = heights.length;27 int[] leftLower = new int[n];28 int[] rightLower = new int[n];29 30 IntStack stk = new IntStack(n + 1);31 for(int i = 0; i < n; i++)32 {33 int h = heights[i];34 while(stk.size() > 0 && heights[stk.peek()] > h)35 {36 rightLower[stk.pop()] = i;37 }38 stk.push(i);39 }40 while(stk.size() > 0)41 {42 rightLower[stk.pop()] = n;43 }44 45 for(int i = n - 1; i >= 0; i--)46 {47 int h = heights[i];48 while(stk.size() > 0 && heights[stk.peek()] > h)49 {50 leftLower[stk.pop()] = i;51 }52 stk.push(i);53 }54 while(stk.size() > 0)55 {56 leftLower[stk.pop()] = -1;57 }58 59 int max = 0;60 for(int i = 0; i < n; i++)61 {62 int area = (rightLower[i] - leftLower[i] - 1) * heights[i];63 max = Math.max(max, area);64 }65 66 // System.out.println(Arrays.toString(heights) + " : " + max);67 return max;68 }69 70 private static class IntStack{71 int[] arr;72 int top = 0;73 public IntStack(int capacity)74 {75 arr = new int[capacity];76 }77 public void push(int val)78 {79 arr[top++] = val;80 }81 public int pop()82 {83 return arr[--top];84 }85 public int peek()86 {87 return arr[top - 1];88 }89 public int size(){90 return top;91 }92 }93 }