边界都是1的最大正方形大小

题目描述
给定一个N \times NN×N的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度、
例如
0 1 1 1 1
0 1 0 0 1
0 1 0 0 1
0 1 1 1 1
0 1 0 1 1
其中，边框全是1的最大正方形的大小为4 \times 44×4，所以返回4
[要求]
时间复杂度为O(n^3)O(n
3
)，空间复杂度为O(n^2)O(n
2
)

思路1：枚举所有子矩阵，时间复杂度 O(nm) * O(nm)
基于 思路一可以变为 枚举所有“正方形矩阵”,这个时候如果我们能够知道 左上角A，左下角B ，右上角C 三个点的位置，并知道相应的边长，就可以在O(min(m,n)) 中得到答案
所以有了思路二：
对矩阵进行预处理
假设我们有两个矩阵 right ，down
right[i][j] 标示 arr[i][j] 点上，向右有多少个连续的1
down[i][j] 标示 arr[i][j] 点上，向下有多少个连续的1
则
已经知道的左上角，只需要求得 k = min(right ,down ) ,然后 使得
down[i][j+k] >=k && right[i+k][j] >=k 即可 保证 点 i，j 可以构成一个长度为k 的正方形
如果不是就进行收缩 k--
整体时间复杂度 O(N^3) 空间复杂度 O(N^2)

package main
import (
    "fmt"
    //"os"
    //"strconv"
    //"bufio"
)
type node struct {
    right int 
    down int 
}
func main(){
    var n int
    fmt.Scanf("%d",&n)
    arr := make([][]int,n)
    dp := make([][]node,n)
    for i:=0;i<n;i++{
        arr[i] = make([]int,n)
        dp[i] = make([]node,n)
        for j:=0;j<n;j++{
            fmt.Scanf("%d",&arr[i][j])
        }
    }
    //构造dp 数据记录当前点的 right，down 值，注意当前点如果为0 默认取0，不记录
    for i:=n-1;i>=0;i--{
        num := 0
        for j:=n-1;j>=0;j--{
            if arr[j][i] == 0{
                num = 0
                continue
            }
            dp[j][i].down = num
            num ++
        }
        num = 0
        for k:=n-1;k>=0;k--{
            if arr[i][k] == 0 {
                num = 0
                continue;
            }
            dp[i][k].right = num
            num++
        }
    }
    helper(arr,dp,n)
    return 
}
//对预处理好的数组进行计算
func helper(arr [][]int ,dp [][]node,n int ){
    res := 0
    for i:=0;i<n;i++{
        for j:=0;j<n;j++{
            if arr[i][j] == 0{
                continue
            }
            minLen := dp[i][j].right
            if minLen > dp[i][j].down{
                minLen = dp[i][j].down
            }
            //fmt.Println(minLen)
            for k:=minLen;k>=0;k--{
                //判断是否越界 本题中 理论不需要
                if i+k >=n || j+k >=n{
                    continue
                }

                //判断是否是正方形
                if dp[i+k][j].right >= k && dp[i][j+k].down >= k {
                    if k > res {
                        res = k
                        //一旦是了即可退出，因为第一个是的一定是这一轮最大的
                        break
                    }
                }
            }
        }
    }
    //记得加上自身
    if res != 0 {
        res += 1
    }
    fmt.Println(res)
    return 

}