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.
Solution:
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] left = new int[n], right = new int[n], height = new int[n];
for(int j=0; j<n; j++) right[j] = n;
int ans = 0;
for(int i=0; i<m; i++){
int curLeft=0, curRight=n;
for(int j=0; j<n; j++){
if(matrix[i][j]=='1'){
height[j]++;
left[j] = Math.max(left[j], curLeft);
} else {
height[j] = 0;
left[j] = 0;
curLeft = j + 1;
}
if(matrix[i][n-1-j]=='1'){
right[n-1-j] = Math.min(right[n-1-j], curRight);
} else {
right[n-1-j] = n;
curRight = n-1-j;
}
}
for(int j=0; j<n; j++) ans = Math.max(ans, (right[j]-left[j])*height[j]);
}
return ans;
}
}