Largest rectangle of 1's in 2d binary matrix
There is a problem to find the maximum area of the 1 in the 0-1 matrix. In this problem there are two cases:
area to be measure is of shape square. that's simple one by DP.
area to be measure is of the shape of rectangle. i am not able to think a optimal solution for this.
Example:
010101
101001
111101
110101
The largest rectangle has an area of 4 (3rd row , 5th column and one more in 3rd,4th row). Can we also get all those rectangle ?
I'll step through a few solutions of increasing difficulty / decreasing runtime complexity.
First, a brute force solution. Generate every possible rectangle. You can do this by iterating through every pair of points (r1,c1) (r2,c2) with r1 ≤ r2 and c1 ≤ c2 (can be done with 4 for loops). If a rectangle does not contain a 0, you compare the area to the largest area found so far. This is an O(R^3C^3).
We can speed up the valid rectangle check to O(1). We do this by doing a DP where dp(r, c) stores the number of 0's in the rectangle ((1, 1), (r, c)).
Then the number of 0's in ((r1, c1), (r2, c2)) is
You can then check if a rectangle is valid by nzeroes(r1,c1,r2,c2) == 0.
There is an O(R^2C) solution for this using a simple DP and a stack. The DP works per column, by finding the number of 1 cells above a cell until the next 0. The dp is as follows:
dp(r, 0) = 0 dp(r, c) = 0 if matrix[r][c] == 0 dp(r, c) = dp(r-1, c) + 1 otherwise
You then do the following:
area = 0
for each row r:
stack = {}
stack.push((height=0, column=0))
for each column c:
height = dp(r, c)
c1 = c
while stack.top.height > height:
c1 = stack.top.column
stack.pop()
if stack.top.height != height:
stack.push((height=height, column=c1))
for item in stack:
a = (c - item.column + 1) * item.height
area = max(area, a)
It is also possible to solve the problem in O(RC) using three DP's:
The three recurrence relations are:
h(r, c) = h(r-1, c)+1 otherwise
l(r, 0) = 0
l(r, c) = min(l(r − 1, c), c − p) otherwise
r(r,C+1) = 0
where p is the column of the previous 0 as we populate l from left-right and r from right-left.
The answer is then:
This works because of the observation that the largest rectangle will always touch a 0 (considering the edge as being covered in 0's) on all four sides. By considering all rectangles with at least top, left and right touching a 0, we cover all candidate rectangles. Generate every possible rectangle. You can do this by iterating through every pair of points (r1,c1) (r2,c2) with r1 ≤ r2 and c1 ≤ c2 (can be done with 4 for loops). If a rectangle does not contain a 0, you compare the area to the largest area found so far.
Note: I adapted the above from an answer I wrote up here - refer to the section "Ben's Mom". In that writeup, the 0's are trees. That writeup also has better formatting.
The problem can be reduced to finding the maximum rectangle area in a histogram, multiple times.
After each row, you calculate the histogram built until that row, and that calculate the maximum area rectangle in that histogram.
int maximalRectangle(vector<vector<char> > &mat) {
int rows=mat.size();
if(rows==0)return 0;
int columns = mat[0].size();
int temp[columns];
for(int i=0;i<columns;i++){
temp[i] = mat[0][i]-'0';
}
int maxArea=0;
maxArea = max(maxArea,maxUtil(temp,columns));
// cout<<"before loopn";
// print1d(temp,columns);
for(int i=1;i<rows;i++){
for(int j=0;j<columns;j++){
temp[j] = (mat[i][j]-'0')?temp[j]+1:0;
}
// cout<<"after iteration : "<<i<<endl;
// print1d(temp,columns);
maxArea = max(maxArea,maxUtil(temp,columns));
// cout<<"maxarea = "<<maxArea<<endl;
}
return maxArea;
}
temp is the histogram in each step and maxutil calculates the max rectanglular area in that histogram.
I would try the following:
(1) Decompose the matrix into connected components (through BFS).
(2) For each connected component, look for the maximal rectangle.
To do (2), I would first look for vertical rectangles: Find the maximal possible width for each consecutive (min_y, max_y), and therefore the area (iteratively, in O(1) per row, just by looking at the min/max of 1's in that row of the connected component). Then I would transpose the matrix, and repeat the process.
The total running time is O(MxN) for BFS, then O(width^2 + height^2) for each connected componenet, for a total of O(MXN + M^2 + N^2).
I wonder what's the asymptotically optimal solution though.
链接地址: http://www.djcxy.com/p/94610.html上一篇: 算法来查找数组中最大的下拉列表
下一篇: 二维矩阵中1的最大矩形