题目来源：
> Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
解题思路：
O(n^3) 算法
一种直接的方法是: 横向记录从左到i, 包括i为1的连续1的长度，然后再纵向去查找以这个连续1长度作为min宽的最大的高度,得到面积。O(n^3)
int getMaxHeight(const vector<vector<int> > &ones, int row, int col)
{
int minWidth = ones[row][col];
int height = 0;
for(int i = row; i >= 0; i--) //up
{
if(ones[i][col] >= minWidth)
++height;
else
break;
}
for(int i = row+1; i < ones.size(); i++)
{
if(ones[i][col] >= minWidth)
++height;
else
break;
}
return height;
}
int maximalRectangle(vector<vector<char> > &matrix)
{
int m = matrix.size(); if(m == 0) return 0;
int n = matrix[0].size();
vector<vector<int> > ones(m, vector<int>(n, 0));//[i][j], 第i行从左到j, 包括j连续1的长度
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(j == 0) ones[i][0] = matrix[i][j] == '1' ? 1 : 0;
else ones[i][j] = matrix[i][j] == '1' ? ones[i][j-1]+1 : 0;
}
int result = 0;
for(int i = 0; i < m; i++)
for(int j = 0; j < n; j++)
{
if(ones[i][j] > 0)
result = std::max(result, ones[i][j] * getMaxHeight(ones, i, j));
}
return result;
}
O(n^2)算法
用栈维护了一个递增(非递减)的序列，当当前索引的元素比栈顶小时，取栈顶元素（并出栈），并将这个元素的高度和当前索引端(快降低了)构成的矩形面积，栈中上升的那段都可以出栈并计算。
int largestRectangleArea(const vector<int> &height)
{
int result = 0;
stack<int> index;
for(int i = 0; i < height.size(); i++)
{
if(index.empty() || height[index.top()] <= height[i] )
index.push(i);
else
{
while(!index.empty() && height[index.top()] >= height[i])
{
auto t = index.top();
index.pop();
result = std::max(result, height[t] * (index.empty() ? i : (i-1)-index.top()));
}
index.push(i);//Do not forget.
}
}
return result;
}
int maximalRectangle(vector<vector<char> > &matrix)
{
int m = matrix.size(); if(m == 0) return 0;
int n = matrix[0].size();
vector<vector<int> > ones(m, vector<int>(n, 0));
int result = 0;
for(int i = 0; i < m; i++)
{
for(int j = 0; j < n; j++)
{
if(i == 0) ones[0][j] = matrix[i][j] == '1' ? 1 : 0;
else ones[i][j] = matrix[i][j] == '1' ? ones[i-1][j]+1 : 0;
}
ones[i].push_back(-1);
result = std::max(result, largestRectangleArea(ones[i]));
}
return result;
}
[0,2,3,]-->[0,2,]
4*(4-1-2)=8.
[0,2] --> [0]
3*(4-1-0)=9. !!max
[0] -->[]
2*(4)=8.
上面代码还可以优化下内存空间, 用O(n)n为列数量。
int maximalRectangle2(vector <string > & matrix)
{
int m = matrix.size(); if (m == 0) return 0;
int n = matrix[0].size(); if (n == 0) return 0;
vector< int> height(n+1, 0);
int maxArea = 0;
for(int row = 0; row < m; row++)
{
for(int col = 0; col < n; col++)
{
if(matrix [row][col] == '1')
height[col] += 1;
else
height[col] = 0;
}
height[n] = -1; //dummy one
maxArea = std::max(maxArea, largestRectangleArea(height));
}
return maxArea;
}
O(n^2)算法 思路2
int maximalRectangle(vector<vector<char> > &matrix)
{
int m = matrix.size(); if(m == 0) return 0;
int n = matrix[0].size();
int result = 0;
vector<int> leftMax(n, -1);
vector<int> rightMin(n, n);
vector<int> height(n, 0);
for(int i = 0; i < m; i++)
{
int left = -1, right = n;
for(int j = 0; j < n; j++)
{
if(matrix[i][j] == '1'){
++height[j];
leftMax[j] = std::max(leftMax[j], left);
}else{
left = j;
height[j]=0; leftMax[j]=-1; rightMin[j]=n;
}
}
for(int j = n-1; j >= 0; j--)
{
if(matrix[i][j] == '1'){
rightMin[j] = std::min(rightMin[j], right);
result = std::max(result, height[j]*(rightMin[j]-leftMax[j]-1));
}else{
right = j;
}
}
}
return result;
}