2021-12-11：最大正方形。在一个由 ‘0‘ 和 ‘1‘ 组成的二维矩

原创

福大大架构师每日一题

发布于 2021-12-12 09:35:44

4690

发布于 2021-12-12 09:35:44

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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

答案2021-12-12：

动态规划。dpi是正方形右下角的点，值是边长。dpi依赖左，上，左上。

时间复杂度：O(N*M)。

空间复杂度：O(N*M)。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    m := [][]byte{
        {1, 1, 1, 0},
        {1, 1, 1, 1},
        {1, 1, 1, 1},
        {1, 1, 1, 1},
    }
    ret := maximalSquare(m)
    fmt.Println(ret)
}

func maximalSquare(m [][]byte) int {
    if len(m) == 0 || len(m[0]) == 0 {
        return 0
    }
    N := len(m)
    M := len(m[0])
    dp := make([][]int, N+1)
    for i := 0; i < N+1; i++ {
        dp[i] = make([]int, M+1)
    }
    max := 0
    for i := 0; i < N; i++ {
        if m[i][0] == 1 {
            dp[i][0] = 1
            max = 1
        }
    }
    for j := 1; j < M; j++ {
        if m[0][j] == 1 {
            dp[0][j] = 1
            max = 1
        }
    }
    for i := 1; i < N; i++ {
        for j := 1; j < M; j++ {
            if m[i][j] == 1 {
                dp[i][j] = getMin(
                    getMin(dp[i-1][j],
                        dp[i][j-1]),
                    dp[i-1][j-1]) + 1
                max = getMax(max, dp[i][j])
            }
        }
    }
    return max * max
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}
func getMin(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

执行结果如下：