221 Maximal Square 最大正方形
Description:
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 0
1 1 1 1 1
1 0 0 1 0
Output: 4
题目描述:
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
示例 :
输入:
1 0 1 0 0
1 0 1 1 0
1 1 1 1 1
1 0 0 1 0
输出: 4
思路:
动态规划
一个正方形只用考虑其边长
dp[i][j]表示 matrix[i - 1][j - 1]能够得到的最大的正方形的边长
由于 dp[i][j]受限于左边, 左上角和上方的边长, 可以得到状态转移方程:
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j]), matrix[i - 1][j - 1] == '1'
dp[i][j] = 0, matrix[i - 1][j - 1] == '0'
可以看到, 每次更新只需要临近两行, 可以将左上角的记录下来, 这样每次只需要一行就可以更新, 空间复杂度可以压缩到 O(n)
时间复杂度O(mn), 空间复杂度O(n), 其中 m为 matrix的大小, n为 matrix[0]的大小
代码:
C++:
class Solution
{
public:
int maximalSquare(vector<vector<char>>& matrix)
{
int result = 0, temp = 0;
if (matrix.empty()) return result;
vector<int> dp(matrix[0].size() + 1, 0);
for (auto &row : matrix)
{
temp = 0;
for (int j = 1; j < matrix[0].size() + 1; j++)
{
int next = dp[j];
if (row[j - 1] == '1')
{
dp[j] = 1 + min({dp[j - 1], temp, dp[j]});
result = max(result, dp[j]);
}
else dp[j] = 0;
temp = next;
}
}
return result * result;
}
};
Java:
class Solution {
public int maximalSquare(char[][] matrix) {
if (matrix.length == 0) return 0;
int dp[][] = new int[matrix.length + 1][matrix[0].length + 1], result = 0;
for (int i = 1; i < matrix.length + 1; i++) for (int j = 1; j < matrix[0].length + 1; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i - 1][j - 1], dp[i][j - 1]));
result = Math.max(result, dp[i][j]);
}
}
return result * result;
}
}
Python:
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
dp, result = [[0] * (len(matrix[0]) + 1) for _ in range(len(matrix) + 1)], 0
for i in range(1, len(matrix) + 1):
for j in range(1, len(matrix[0]) + 1):
if matrix[i - 1][j - 1] == '1':
dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j])
result = max(result, dp[i][j])
return result ** 2
