Question Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
For example, given the following matrix: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Return 6.
思路
方法一： 转换为Largest Rectangle in Histogram，求柱状图中最大矩阵的面积。 例如： 左边是原始矩阵， 右边对应转换后的柱状图，（行与行对应，相应位置的数表示该位置的高度） 1 0 1 0 0 -----> 1 0 1 0 0 1 0 1 1 1 -----> 2 0 2 1 1 1 1 1 1 1 -----> 3 0 3 2 2 1 0 0 1 0 -----> 4 0 0 3 0代码如下：
class Solution { public: int largestRectangleArea(const vector<int>& bar){ int ret=0; int len=bar.size(); stack<int> s; for(int i=0; i<len;++i){ while(!s.empty() && bar[s.top()] > bar[i]){ int h=bar[s.top()]; s.pop(); int left=s.empty()?-1:s.top(); if(ret<(i-left-1)*h) ret=h*(i-left-1); } s.push(i); } return ret; } int maximalRectangle(vector<vector<char>>& matrix) { if(matrix.empty()) return 0; int maxA=0; int row=matrix.size(), col=matrix[0].size(); vector<int> bar(col+1,0); for(int i=0; i<row; ++i){ for(int j=0; j<col; ++j){ if(matrix[i][j]=='1') ++bar[j]; else bar[j]=0; } maxA=max(maxA,largestRectangleArea(bar)); } return maxA; } }; 动态规划解法（详见这里）。 点(i, j) 所在的矩阵的面积为height[i, j]*(right[i, j]-left[i, j])。其中height[i, j]统计当前位置及往上’1’的数量；left和right是高度是当前点的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'代码如下：
int maximalRectangle(vector<vector<char>>& matrix) { if(matrix.empty()) return 0; int maxA=0; int row=matrix.size(), col=matrix[0].size(); vector<int> left(col,0),height(col,0), right(col,col); for(int i=0; i<row; ++i){ int curleft=0,curright=col; for(int j=0; j<col; ++j){ if(matrix[i][j]=='1') height[j]=++height[j]; else height[j]=0; if(matrix[i][j]=='1') left[j]=max(left[j],curleft); else{ left[j]=0;curleft=j+1; } } for(int j=col-1; j>=0; --j){ if(matrix[i][j]=='1') right[j]=min(right[j],curright); else{ right[j]=col; curright=j; } } for(int j=0; j<col;++j) maxA=max(maxA,(right[j]-left[j])*height[j]); } return maxA; }