一、题目描述：
给定一个N*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*4，所以返回4。
二、思路分析：
在N * N 的矩阵中，想要获取一个正方形，它的数量级为O(n^3)。两个循环可以确定左上角的点，再使用一个循环列举它的边长。 如果确定边框全是1的话还需要再遍历正方形，来判断它是否是边长为1的正方形。
在遍历边长的时候，我们可以利用两个预处理数组，将复杂度降低一个等级。定义right[i][j]记录右边连续出现1的个数，down[i][j]记录下方连续出现1的个数。
网络异常，图片无法展示
|
注意点
在预处理数组的时候，需要初始化两个数组right、down。一开始使用fill填充0的时候，发现获取预处理数组的结果不对，后来搜索问题后，发现fill属于浅拷贝，对象指向的都是同一个内存地址，一个变动，多个一起变动。
所以后来使用了from来初始化数组。
三、AC 代码：
function calculate(m) { let n = m.length let right = Array.from(Array(n), () => Array.from(Array(n), () => 0)) let down = Array.from(Array(n), () => Array.from(Array(n), () => 0)) setBorderMap(m, right, down) for (let size = Math.min(m.length, m[0].length); size != 0; size--) { if (hasSizeBorder(size, right, down)) { return size } } return 0 } function hasSizeBorder(size, right, down) { for (let i = 0; i <= right.length - size; i++) { for (let j = 0; j <= right[0].length - size; j++) { if ( right[i][j] >= size && down[i][j] >= size && right[i + size - 1][j] >= size && down[i][j + size - 1] >= size ) { return true } } } return false } function setBorderMap(m, right, down) { let c = m[0].length, r = m.length if (m[r - 1][c - 1] === 1) { right[r - 1][c - 1] = 1 down[r - 1][c - 1] = 1 } for (let i = r - 2; i != -1; i--) { if (m[i][c - 1] == 1) { right[i][c - 1] = 1 down[i][c - 1] = down[i + 1][c - 1] + 1 } } for (let i = c - 2; i != -1; i--) { if (m[r - 1][i] == 1) { right[r - 1][i] = right[r - 1][i + 1] + 1 down[r - 1][i] = 1 } } for (let i = r - 2; i >= 0; i--) { for (let j = c - 2; j >= 0; j--) { if (m[i][j] === 1) { right[i][j] = right[i][j + 1] + 1 down[i][j] = down[i + 1][j] + 1 } } } }
四、总结：
利用预处理数组，降低复杂度。可以避免三次循环后再使用一个循环确定边长是否均为1。
作者：ClyingDeng
链接：https://juejin.cn/post/6952738527066980388
来源：稀土掘金
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
