最大正方形问题

最大,正方形,问题 · 浏览次数 : 48

小编点评

**最大正方形问题作者：Grey原文地址：博客园：最大正方形问题CSDN：最大正方形问题题目描述** **题目描述：** 在由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 **思路：** * 定义二维数组 `dp`，其中 `dp[i][j]` 表示正方形必须以 `i, j` 作为右下角的情况下，哪个正方形内部都是 1 且最大。 * 考虑普遍位置，并根据左右、上、左上三个位置的值来计算 `dp[i][j]` 的值。 * 最外层循环从 `1` 到 `m` 行，从 `1` 到 `n` 列遍历矩阵。 * `dp[i][j]` 的值取决于 `dp[i - 1][j - 1]`, `dp[i - 1][j]` 和 `dp[i][j - 1]` 的最小值。 * `dp[i][j]` 的最终结果就是所有包含 '1' 的最大正方形的面积之和。 **代码：** ```python class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: if not matrix or len(matrix) == 0 or len(matrix[0]) == 0: return 0 m, n = len(matrix), len(matrix[0]) # Initialize dp matrix dp = [[0] * n for _ in range(m)] for _ in range(n)] # Initialize first row and first column for i in range(m): dp[i][0] = matrix[i][0] == '1' max = max(dp[i][0], i) for i in range(n): dp[0][i] = matrix[0][i] == '1' max = max(dp[0][i], i) # Fill dp matrix for i in range(1, m): for j in range(1, n): dp[i][j] = matrix[i][j] == '1' if dp[i - 1][j - 1] == dp[i - 1][j] else min(dp[i - 1][j - 1], dp[i - 1][j]) + 1 return max * max ```

正文

最大正方形问题

作者：Grey

原文地址：

博客园：最大正方形问题

CSDN：最大正方形问题

题目描述

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

题目链接见：LeetCode 221. Maximal Square

主要思路

本题思路比较简单，可以定义一个二维数组dp，二维数组dp的规模和原始矩阵的规模一样。

int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];

其中dp[i][j]表示正方形必须以 i, j 作为右下角的情况下，哪个正方形内部都是 1 且最大。

有一个很显而易见的结论，如果matrix[i][j] == '0'，则dp[i][j] = 0，接下来是 base case，

第一行和第一列的值很容易可以得到

  for (int i = 0; i < m; i++) {
    dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
    max = Math.max(dp[i][0], max);
}
for (int i = 0; i < n; i++) {
    dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
     max = Math.max(dp[0][i], max);
}

注：max变量用于记录全局最大值。

考虑普遍位置，如下图

观察dp[i][j]周围的位置依赖，有如下两种情况

其中dp[i-1][j]表示的区域是绿色部分的正方形，dp[i-1][j-1]表示的区域是红色部分的正方形，dp[i][j-1]表示蓝色区域部分的正方形，基于上述上个位置的值，可以得到dp[i][j]的值，即dp[i][j]依赖其左边一个位置，上面一个位置，左上角位置。

代码如下

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = matrix[i][j] == '1' ? Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1 : 0;
                max = Math.max(dp[i][j], max);
            }
        }

完整代码见

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (null == matrix || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int max = 0;
        // tips 正方形必须以i,j作为右下角情况，哪个正方形内部都是1且最大
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] == '1' ? 1 : 0;
            max = Math.max(dp[i][0], max);
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = matrix[0][i] == '1' ? 1 : 0;
            max = Math.max(dp[0][i], max);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = matrix[i][j] == '1' ? Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i][j - 1]) + 1 : 0;
                max = Math.max(dp[i][j], max);
            }
        }
        return max * max;
    }
}

算法和数据结构笔记