【多维动态规划】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
解题思路
- 使用一个二维数组 dp，其中 dp[i][j] 表示以矩阵位置 (i, j) 为右下角的最大正方形的边长。
- 为了计算 dp[i][j] 的值，需要考虑 matrix[i][j] 是否为 ‘1’，如果是 ‘0’，
则 dp[i][j] = 0 - 否则 dp[i][j] 的值由其上方、左方和左上方的 dp 值决定：
dp[i][j]=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1
Java实现
public class MaximalSquare {public int maximalSquare(char[][] matrix) {if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {return 0;}int rows = matrix.length;int cols = matrix[0].length;int[][] dp = new int[rows + 1][cols + 1];int maxSide = 0;for (int i = 1; i <= rows; i++) {for (int j = 1; j <= cols; j++) {if (matrix[i - 1][j - 1] == '1') {dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;maxSide = Math.max(maxSide, dp[i][j]);}}}return maxSide * maxSide;}// 测试用例public static void main(String[] args) {MaximalSquare solution = new MaximalSquare();char[][] matrix1 = {{'1', '0', '1', '0', '0'},{'1', '0', '1', '1', '1'},{'1', '1', '1', '1', '1'},{'1', '0', '0', '1', '0'}};System.out.println(solution.maximalSquare(matrix1)); // 期望输出: 4char[][] matrix2 = {{'0', '1'},{'1', '0'}};System.out.println(solution.maximalSquare(matrix2)); // 期望输出: 1char[][] matrix3 = {{'0'}};System.out.println(solution.maximalSquare(matrix3)); // 期望输出: 0}
}时间空间复杂度
-
时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数，需要遍历矩阵中的每一个元素。
-
空间复杂度：O(m * n)，使用了一个大小为 m * n 的 dp 数组。