前言
解法十分精彩
正文
问题来源
本问题来自leetcode上的85题。
问题描述
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 :
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
分析：
leetcode 85
思路同样是从第一行开始一行一行地处理，使[i, j]处最大子矩阵的面积是(right(i, j)-left(i, j))*height(i, j)。其中height统计当前位置及往上’1’的数量；left和right是高度是当前点的height值得左右边界，即是以当前点为中心，以height为高度向两边扩散的左右边界。
递推公式如下：
left(i, j) = max(left(i-1, j), cur_left);
right(i, j) = min(right(i-1, j), cur_right);
height(i, j) = height(i-1, j) + 1, if matrix[i][j]=='1';
height(i, j) = 0, if matrix[i][j]=='0'.
自己手撸的C代码
#define min(x,y) ((x)<(y)?(x) : (y))
#define max(x,y) ((x)>(y)?(x) : (y))
int maximalRectangle(char** matrix, int matrixRowSize, int matrixColSize) {
int *left = NULL;
int *right = NULL;
int *height = NULL;
int result = 0;
int i,j;
int lbegin,rbegin;
//申请内存
left = (int*)malloc(sizeof(int)*matrixColSize);
right = (int*)malloc(sizeof(int)*matrixColSize);
height = (int*)malloc(sizeof(int)*matrixColSize);
//init
for(i=0;i<matrixColSize;i++)
{
left[i] = 0;
right[i] = matrixColSize;
height[i] = 0;
}
//dp working
for(i=0;i<matrixRowSize;i++)
{
lbegin = 0;
rbegin = matrixColSize;
for(j=0;j<matrixColSize;j++)
{
if(matrix[i][j]=='0')
{
left[j] = 0;
lbegin = j + 1;
}
else
{
left[j] = max(left[j],lbegin);
}
}
for(j=matrixColSize-1;j>=0;j--)
{
if(matrix[i][j]=='0')
{
right[j] = matrixColSize;
rbegin = j ;
}
else
{
right[j] = min(right[j],rbegin);
}
}
for(j=0;j<matrixColSize;j++)
{
if(matrix[i][j]=='0')
{
height[j] = 0;
}
else
{
height[j] += 1;
result = max(result,height[j]*(right[j]-left[j]));
}
}
}
//释放内存
free(left);
free(right);
free(height);
return result;
}
总结：
与大神们的差距不是一星半点。
结语
坚持不懈。
