Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
40 lines (37 sloc) 1.05 KB
problem:
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
--------------------------------------------------------------------------
solution:
//DP。用f[i][j]来记录以i行j列为结尾,在当前行j列往前连续的1的个数。
//然后再一个O(n^3)的循环来找以(i, j)为右下角的矩形最大的1的面积。
int maximalRectangle(vector<vector<char> > &matrix)
{
int f[1000][1000];
int m = matrix.size();
if(m == 0)
return 0;
int n = matrix[0].size();
if(n == 0)
return 0;
for(int i = 0; i < m; ++i)
f[i][0] = (matrix[i][0] == '1' ? 1 : 0);
for(int i = 0; i < m; ++i)
for(int j = 1; j < n; ++j)
f[i][j] = (matrix[i][j] == '1' ? f[i][j - 1] + 1 : 0);
int area = 0;
for(int i = 0; i < m; ++i)
for(int j = 0; j < n; ++j)
{
int k = i; //k控制以[i,j]为右下角矩形的高
int width = INT_MAX;
while(k >= 0)
{
if(f[k][j] == 0)
break;
width = min(width, f[k][j]);
area = max(area, width * (i - k + 1));
k--;
}
}
return area;
}