问题描述
给定一个只包含 0 和 1 的矩阵，要求找出其中最大的正方形的面积。题目链接：**点我**
样例输入输出
输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：4
输入：matrix = [[“0”,”1”],[“1”,”0”]]
输出：1
问题解法
使用动态规划，用 dp[i][j] 表示以 (i, j) 为右下角的所有正方形中最大正方形的边长度，则动态转移方程为 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1(其中，dp[i][j] == 1)，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution
{
public int maximalSquare(char[][] matrix)
{
int[][] dp = new int[matrix.length][matrix[0].length];
int edge = 0;
for (int i = 0; i < matrix.length; i++)
{
if (matrix[i][0] == '1')
{
dp[i][0] = 1;
edge = 1;
}
}
for (int j = 0; j < matrix[0].length; j++)
{
if (matrix[0][j] == '1')
{
dp[0][j] = 1;
edge = 1;
}
}
for (int i = 1; i < matrix.length; i++)
{
for (int j = 1; j < matrix[0].length; j++)
{
if (matrix[i][j] == '0')
{
dp[i][j] = 0;
continue;
}
dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
edge = Math.max(edge, dp[i][j]);
}
}
return edge * edge;
}
}
|