LeetCode [85] Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

class Solution { public int maximalRectangle(char[][] matrix) { int m = matrix.length; if(m==0) return 0; int n = matrix[0].length; if(n==0) return 0; int[] h = new int[n];//h[j]: height at [i, j] int[] l = new int[n];//l[j]: left bound for height at [i, j] int[] r = new int[n];//r[j]: right bound for height at [i, j] Arrays.fill(r, n-1); int maxArea = 0; for(int i=0; i<m; ++i){ int lb = 0;//left bound at this layer int rb = n-1;//right bound at this layer for(int j=0; j<n; ++j){ if(matrix[i][j]=='0'){ h[j] = 0; }else{ h[j]++; } } for(int j=0; j<n; ++j){ if(matrix[i][j]=='0'){ lb = j+1;//current left bound is possibly the ceil to the right of [i,j] l[j] = 0;//relax the left bound for [i, j]. The next layer's left bound will be determined by next layer's lb. }else{ l[j] = Math.max(l[j], lb); } } for(int j=n-1; j>=0; --j){ if(matrix[i][j]=='0'){ rb = j-1; r[j] = n-1; }else{ r[j] = Math.min(r[j], rb); } } for(int j=0; j<n; ++j){ int area = h[j] * (r[j]-l[j]+1); maxArea = Math.max(area, maxArea); } } return maxArea; } }