这道题值得hard的难度。
看了答案写出来的。值得多看几遍。
public class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix==null || matrix.length==0 || matrix[0].length==0)
return 0;
int m = matrix.length;
int n = matrix[0].length;
int left[] = new int[n], right[] = new int[n], height[] = new int[n];
Arrays.fill(left,0); Arrays.fill(right,n); Arrays.fill(height,0);
int max_area = 0;
for(int i=0; i<m; i++) {
int cur_left = 0, cur_right = n;
// calculate height;
for(int j=0; j<n; j++) {
if(matrix[i][j]=='1')
height[j]++;
else height[j] = 0;
}
// calculate left;
for(int j=0; j<n; j++) {
if(matrix[i][j]=='1')
left[j] = Math.max(left[j], cur_left);
else {
left[j] = 0; // set back to "0", to prepare for next iteration.
cur_left = j+1;
}
}
// calculate right;
for(int j=n-1; j>=0; j--) {
if(matrix[i][j]=='1')
right[j] = Math.min(right[j], cur_right);
else {
right[j] = n; // set back to "n", to prepare for next iteration.
cur_right = j;
}
}
// max_area;
for(int j=0; j<n; j++){
int new_area = (right[j] - left[j]) * height[j];
max_area = Math.max(max_area, new_area);
}
}
return max_area;
}
}
