Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
Example:
Input: 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0 Output: 4
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int row = matrix.size();
if (row == 0) {
return 0;
}
int col = matrix[0].size();
int ans = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (matrix[i][j] != '0') {
if (i != 0 && j != 0) {
matrix[i][j] = min(matrix[i-1][j-1], min(matrix[i - 1][j],
matrix[i][j - 1])) + 1;
}
ans = max(ans, matrix[i][j] - '0');
}
}
}
return ans * ans;
}
};
No comments:
Post a Comment