121.最大正方形

题目

在一个由 '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

思路：动态规划，从左上角开始推算

我们想知道整个矩阵中最大的全1正方形有多大，但可以先解决更小的问题：以每个格子为右下角，能形成的最大正方形边长是多少？

状态定义

设 dp[i][j] 表示以 matrix[i][j] 为右下角的最大全1正方形的边长。

状态转移

如果 matrix[i][j] == '1':
    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
否则：
    dp[i][j] = 0

边界条件

第一行（i=0）和第一列（j=0）：dp[i][j] = matrix[i][j] - '0'（即如果格子是 '1' 则为1，否则为0）。

class Solution {
    fun maximalSquare(matrix: Array<CharArray>): Int {
        val rows = matrix.size
        val cols = matrix[0].size
        val dp = Array(rows) { IntArray(cols) }
        var maxSide = 0

        for (i in 0 until rows) {
            for (j in 0 until cols) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1
                    } else {
                        dp[i][j] = minOf(
                            dp[i-1][j],
                            dp[i][j-1],
                            dp[i-1][j-1]
                        ) + 1
                    }
                    maxSide = maxOf(maxSide, dp[i][j])
                }
            }
        }
        return maxSide * maxSide
    }
}

复杂度

• 时间复杂度:
• 空间复杂度:

• 下一题

• 邮箱 ：charon.chui@gmail.com
• Good Luck!