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