【LeetCode】221.最大正方形

题目

在一个由 ‘0' 和 ‘1' 组成的二维矩阵内，找到只包含 ‘1' 的最大正方形，并返回其面积。

示例 1：

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

示例 2：

输入：matrix = [["0","1"],["1","0"]]
输出：1

示例 3：

输入：matrix = [["0"]]
输出：0

提示：

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] 为 ‘0' 或 ‘1'

解答

源代码

class Solution {public int maximalSquare(char[][] matrix) {int maxSide = 0;int[][] dp = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (matrix[i][j] == '1') {if (i == 0 || j == 0) {dp[i][j] = 1;} else {dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;}}maxSide = Math.max(maxSide, dp[i][j]);}}return maxSide * maxSide;}
}

总结

隐隐觉得是动态规划，但是不知道怎么根据之前的dp值推算下一个dp值，看了题解学习到了新的思路：dp[i][j] = min(dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]) + 1。