一天一道LeetCode
本系列文章已全部上传至我的github，地址：ZeeCoder‘s Github
欢迎大家关注我的新浪微博，我的新浪微博
欢迎转载，转载请注明出处
（一）题目
Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.
（二）解题
题目大意：给定一个二值矩阵，计算矩阵里面包含1的所有子矩阵的最大面积。
例如：
1000
1101
1111
1111
构成的矩形有第0列面积4，第2，3行面积8等等。
那么我们思考一下如何找到这些矩形，并求出他们的面积呢？
对于(i,j)我们已它为矩形的左上角，那么需要找出，它的向右延伸有多少个1，它向下延伸有多少个1，再就是每一行向右延伸有多少个1，如(1,0)向右延伸2个1，向下延伸3个1，那么(2,0)，(3,0)向右延伸均大于2，故这个矩形的面积为6。
class Solution {
public:
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int row = matrix.size();
int col = matrix[0].size();
vector<vector<int>> sameRowNum;//存放当前点向下延伸多少个1
vector<vector<int>> sameColNum;//存放当前点向右延伸多少个1
for (int i = 0; i < row; i++)
{
vector<int> tmp(col, 0);
sameColNum.push_back(tmp);
sameRowNum.push_back(tmp);
}
for (int i = 0; i < row; i++)//计算sameRowNum
{
for (int j = 0; j < col; )
{
if (matrix[i][j] == '1') {
int t = j;
int count = 0;
while (t < col&&matrix[i][t++] == '1') count++;//计算多少个1
while (j<t) sameColNum[i][j++] = count--;//赋值
}
else j++;
}
}
for (int i = 0; i < col; i++)
{
for (int j = 0; j < row; )
{
if (matrix[j][i] == '1') {
int t = j;
int count = 0;
while (t < row&&matrix[t++][i] == '1') count++;//计算多少个1
while (j<t) sameRowNum[j++][i] = count--;//赋值
}
else j++;
}
}
int maxArea = 0;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col;j++ )
{
if (matrix[i][j]=='1')
{
int t = i;
int mincol = sameColNum[i][j];
while (t < row&&t < i + sameRowNum[i][j]) {
mincol = mincol < sameColNum[t][j] ? mincol : sameColNum[t][j];//依次计算矩形面积
int area = mincol*(t-i+1);
maxArea = max(maxArea, area);//求最大值
t++;
}
}
}
}
return maxArea;
}
};