LeetCode221.动态规划算法图文详解(Kotlin语言):二维矩阵中找到只包含 1 的最大正方形

一个会写诗的程序员

发布于 2020-04-24 12:12:45

1K0

发布于 2020-04-24 12:12:45

文章被收录于专栏：一个会写诗的程序员的博客

LeetCode221.动态规划算法图文详解(Kotlin语言):二维矩阵中找到只包含 1 的最大正方形

题目描述

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

示例:

输入:

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

输出: 4

问题求解

1.暴力求解法

源代码

/**
 * 暴力破解法
 */
fun maximalSquare(matrix: Array<CharArray>): Int {
    var ans = 0

    val m = matrix.size

    if (m == 0) return 0

    val n = matrix[0].size
    // 最大边长上限
    val lenBound = Math.min(m, n)

    for (i in 0 until m) { // i rows
        for (j in 0 until n) { // j cols
            if (matrix[i][j] == '1') {
                var squareLength = 1
                var flag = true

                while (i + squareLength < m && j + squareLength < n && flag && squareLength <= lenBound) {

                    for (k in i..(i + squareLength)) {
                        for (t in j..(j + squareLength)) {
                            if (matrix[k][t] == '0') {
                                flag = false
                                break
                            }
                        }

                        if (!flag) { // 如果这个区域出现了 0,那么当前区域就不必循环了,继续下一格 i,j 的循环
                            break
                        }

                    }

                    if (flag) {
                        squareLength++
                    }

                } // end while

                // 正方形的长度
                ans = Math.max(squareLength, ans)

            }
        }
    }
    return ans * ans
}

复杂度分析

时间复杂度：O( (mn)^2 )，最坏情况下，我们需要遍历整个矩阵寻找每个 1。空间复杂度：O(1)，没有使用额外的空间。

2.动态规划(递推法)

我们用一个例子来解释这个方法：

origin matrix:

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

transfer matrix: f(i,j) 表示在 (0,0)->(i,j) 坐标范围内,由 1 组成的最大正方形的边长:

0 1 1 1 0 1 1 2 2 1 0 1 2 3 1 0 1 2 3 2 0 0 1 2 3

我们用 0 初始化另一个矩阵 f，维数和原始矩阵维数相同； f(i,j) : 表示的是由 1 组成的最大正方形的边长；从 (0,0)开始，对原始矩阵中的每一个 1，我们将当前元素的值更新为: f(i, j) = 1 + min(f(i−1, j), f(i−1, j−1), f(i, j−1)) 用一个变量记录当前出现的最大边长，这样遍历一次，找到最大的正方形边长 maxLen，那么结果就是 maxLen^2.

源代码:

fun maximalSquareDP(matrix: Array<CharArray>): Int {
    var ans = 0
    val m = matrix.size
    if (m == 0) return 0
    val n = matrix[0].size
    // 为了方便下标的计算, 矩阵容量多出 1 行 1 列
    val f = Array(m + 1) { IntArray(n + 1) { 0 } }

    for (i in 1..m) {
        for (j in 1..n) {
            if (matrix[i - 1][j - 1] == '1') {
                var minix = Math.min(f[i - 1][j - 1], f[i - 1][j])
                minix = Math.min(f[i][j - 1], minix)
                // f(i,j) 表示坐标(i,j) 范围内, 由 1 组成的最大正方形的边长
                f[i][j] = 1 + minix
                // 找到最大的正方形边长
                ans = Math.max(ans, f[i][j])
            }
        }
    }
    return ans * ans
}

运行测试

val matrix = arrayOf(
    charArrayOf('1', '1', '1', '1', '1', '1', '1', '1'),
    charArrayOf('1', '1', '1', '1', '1', '1', '1', '0'),
    charArrayOf('1', '1', '1', '1', '1', '1', '1', '0'),
    charArrayOf('1', '1', '1', '1', '1', '0', '0', '0'),
    charArrayOf('0', '1', '1', '1', '1', '0', '0', '0')
)
val ans = maximalSquareDP(matrix)
println("ans=$ans")  // ans=16