題目
https://leetcode-cn.com/problems/maximal-square/submissions/
描述
在一個(gè)由 0 和 1 組成的二維矩陣內(nèi)棠涮，找到只包含 1 的最大正方形，并返回其面積。
示例:
輸入:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
輸出: 4
題解
簡(jiǎn)單dp，對(duì)每個(gè)點(diǎn)的(i,j-1) (i-1,j) (i-1,j-1) 三個(gè)點(diǎn)進(jìn)行比較得出以該點(diǎn)的為右下角頂點(diǎn)可以 形成最大的正方形的邊長(zhǎng)
代碼
public static int maximalSquare(char[][] matrix) {
int length = matrix.length;
if (length == 0)
return 0;
int rowLength = matrix[0].length;
int sum = 0;
int[][] dp = new int[length + 1][rowLength + 1];
for (int i = 0; i < length; i++) {
for (int j = 0; j < rowLength; j++) {
if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j] - '0';
} else if (matrix[i][j] == '1') {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]));
}
sum = Math.max(sum, dp[i][j]);
}
}
return sum * sum;
}
結(jié)果
image.png
