|
Analysis: This is not an easy problem and the idea is not straightforward.
Since the question requires the area of all ones region, first we can define the region (rectangle) in the matrix. Any region in the matrix has several basic properties: 1 corner point, width, and length.
Also which corner point it is decide the exact place of the region, here we consider the bottom-right corner point, because we usually scan the matrix from (0,0) to right and down direction. For this problem, we also need to consider the all ones requirement, where all the regions are filled with 1s.
We can then have this data structure:
One 2D array(vector) ones[i][j], where ones[i][j] stores the number of contiguous 1s ended at matrix[i][j], along ith row. e.g. if matrix[i] = 1011101, then ones[i]=1,0,1,2,3,0,1. This array stores the length of the rectangle, for every possible bottom-right corner point.
Having this two values, next is to find the height of the rectangle, as well as keep the all ones requirement.
Start with a corner point [i][j], since it is the bottom right corner, the rectangle search direction is left and up.
For the left we already have the number of contiguous 1s ones[i][j]. How to get the height We need to scan all the values above ones[i][j], it is from i-1 to 0. If meets 0, then stop, else compute the possible rectangle area, and store the max. To compute the area, the minimum length of rectangle should be compared and stores every time.
package Level5;
/**
* Maximal Rectangle
*
* Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
*
*/
public class S85 {
public static void main(String[] args) {
char[][] matrix = {{'0','1'},{'0','1'}};
System.out.println(maximalRectangle(matrix));
}
public static int maximalRectangle(char[][] matrix) {
int rows = matrix.length;
if(rows == 0){
return 0;
}
int cols = matrix[0].length;
// 先计算全1矩阵的宽度
int[][] hOnes = new int[rows][cols]; // horizontal ones
int max = 0; // 最大面积
for(int i=0; i
= 0){
minRowWidth = Math.min(minRowWidth, hOnes[minI][j]);
int area = minRowWidth * (i-minI+1);
max = Math.max(max, area);
minI--;
}
}
}
}
return max;
}
}
|