首页 > 代码库 > 221. Maximal Square
221. Maximal Square
Problem statement:
Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest square containing only 1‘s and return its area.
For example, given the following matrix:
1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0
Return 4.
Solution:
It looks like 85. Maximal Rectangle. But, there is big difference. This is DP problem, however, maximul rectangle needs tricky.
The key point is what we want from DP? The answer is max side length of square.
DP maintains a 2D array, dp[i][j] means the max side of length of square by current position.
Initialization:
dp[0][j] = matrix[0][j] - ‘0‘;dp[i][0] = matrix[i][0] - ‘0‘;
DP formula. and update the max side length for each value.
if(matrix[i][j] == ‘1‘){ dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;}
Return max_size * max_size;
The time complexity is O(n * n)
class Solution {public: int maximalSquare(vector<vector<char>>& matrix) { if(matrix.empty()){ return 0; } int row = matrix.size(); int col = matrix[0].size(); vector<vector<int>> square_size(row, vector<int>(col, 0)); int max_size = 0; for(int i = 0; i < row; i++){ square_size[i][0] = matrix[i][0] - ‘0‘; max_size = max(max_size, square_size[i][0]); } for(int j = 0; j < col; j++){ square_size[0][j] = matrix[0][j] - ‘0‘; max_size = max(max_size, square_size[0][j]); } for(int i = 1; i < row; i++){ for(int j = 1; j < col; j++){ if(matrix[i][j] == ‘1‘){ square_size[i][j] = min(square_size[i - 1][j - 1], min(square_size[i - 1][j], square_size[i][j - 1])) + 1; } max_size = max(max_size, square_size[i][j]); } } return max_size * max_size; }};
221. Maximal Square
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。