class Solution {
vector<vector<char> >* v;
int getArea(int const cornerRow, int const cornerCol){
int maxArea = 0;
int maxX = (*v)[0].size();
for(int row = cornerRow; row < v->size(); ++row){
if ((*v)[row][cornerCol] == '0') break;
for(int x = cornerCol; x < maxX; ++x){
if ((*v)[row][x] == '0'){
maxX = x;
break;
}
}
int area = (maxX-cornerCol) * (row-cornerRow+1);
if (maxArea <area) maxArea = area;
}
return maxArea;
}
public:
int maximalRectangle(vector<vector<char> > &matrix) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if (matrix.empty() || matrix[0].empty()) return 0;
v = &matrix;
int max = 0;
for(int row = 0; row < matrix.size(); ++row)
for(int col = 0; col < matrix[0].size(); ++col){
int area = getArea(row,col);
if (max < area) max = area;
}
return max;
}
};
Solving problems is fun. But solving the same problem over and over is pain. Once solved, forever solved.
sourcecode
Wednesday, December 5, 2012
Maximal Rectangle
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment