题目描述

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

LeetCode 221. Maximal Square

参考资料

https://leetcode-cn.com/problems/maximal-square/solution/ju-zhen-zhong-quan-wei-1-de-zui-da-zheng-fang-xing/

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/maximal-square

Kotlin 开发者社区

国内第一Kotlin 开发者社区公众号，主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。

越是喧嚣的世界，越需要宁静的思考。