leetcode刷题笔记 221题 最大正方形

leetcode刷题笔记 221题 最大正方形

源地址：221. 最大正方形

问题描述：

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

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

//基于动态规划思想处理， dp(i)(j)表示以i、j为右下节点的正方形的最大边长
//初始状态 
//if (i == 0 || j ==0)情况下
//if (matrix(i)(j) == 1) dp(i)(j) = 1
//else dp(i)(j) = 0
//状态转移方程
//if (matrix(i)(j) == 1) dp(i)(j) = math.min(math.min(dp(i-1)(j), dp(i)(j-1)), dp(i-1)(j-1))+1
//else dp(i)(j) = 0
object Solution {
    def maximalSquare(matrix: Array[Array[Char]]): Int = {
        if (matrix.length == 0 || matrix(0).length == 0) return 0
        
        var maxSide = 0
        val rowLength = matrix.length
        val colLength = matrix(0).length
        val dp = Array.ofDim[Int](rowLength,colLength)
        
        for (i <- 0 to rowLength - 1) {
            for (j <- 0 to colLength - 1){
                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
    }
}