LeetCode.1277.统计全为 1 的正方形子矩阵（中等）

题目

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

题解

从基本情况出发

对于某一个点[i, j]，如果它的值是1，那么构成边长为1的正方形。

构成边长为2的正方形需要什么条件？

对于某一个点[i, j]，如果想要构成边长为2的正方形，要知道周围其余3个点是否都是1。

而这3个点的构成有四个方向：

1
2
3

b b    b b    a b    b a
b a    a b    b b    b b
左上    右上   右下    左下

判断的方向太多了，能不能归类简化一下。
可以发现右上、右下、左下的情况，都可以归类为左上的问题，因为它们右下角的点都会遇到左上的情况。

这里还看不出一般规律，继续看边长更大的情况。

怎么快速判断能否构成边长为3的正方形？

对于某一个点[i, j]，如果去一个个检查左上方的点是不是都是1，太麻烦了；因为如果要检查边长更大的正方形，那么往回遍历的点就越多，而且之前遍历过的点都要重复遍历。

能不能利用之前的计算结果呢？
假设side[i][j]表示以[i, j]为右下角的正方形的个数。
个数的统计是通过看是否依次能够成边长为1、2、3、…、n的正方形，所以a[i][j]也表示能形成的最大的正方形的边长。

分析如下的3x3网格：

         col 
a0 a1 a2  0
b0 b1 b2  1
c0 c1 c2  2
 0  1  2 row

从正方形的边界来推理，怎么利用side数组快速判断格子是否为1。

如果想要a2、b2为1，那么side[1][2] >= 2才行，也就是右下角的格子上方至少有2x2的正方形。
如果想要c0、c1为1，那么side[1][2] >= 2才行，也就是右下角的格子左方至少有2x2的正方形。
a0、a1、b0要为1，那么side[1][1] >= 2才行，也就是右下角的格子的左上方至少有2x2的正方形。

如果有两个方向的正方形边长大于2，但有一个方向的正方形边长为1，会怎么影响side[2][2]？
比如

1
2
3

1 1 0
1 1 1
1 1 1

只能取边长最小的这个方向的正方形边长。

规律已经浮现。

状态转移方程

side[i][j] = 1 + minOf(side[i - 1][j], side[i][j - 1], side[i - 1][j - 1])

边界处理

第一行的每个格子没有上面，只能形成边长为1的正方形。
第一列的每个格子没有左面，只能形成边长为1的正方形。

最后结果

side数组每一项累加，就是所有能用1组成的正方形的个数。

复杂度

必须遍历完二维数组所有元素才能完成求解，并且只需要遍历一次，时间复杂度O(mn)。
需要记录side数组，空间复杂度O(mn)。

代码（kotlin)

class Solution {
    fun countSquares(matrix: Array<IntArray>): Int {
        val m = matrix.size
        val n = matrix[0].size
        var count = 0
        val side = Array(m) { IntArray(n) { 0 } }

        side[0][0] = if (matrix[0][0] == 1) 1 else 0
        count += side[0][0]

        for (i in 1 until m) {
            side[i][0] = if (matrix[i][0] == 1) 1 else 0
            count += side[i][0]
        }

        for (j in 1 until n) {
            side[0][j] = if (matrix[0][j] == 1) 1 else 0
            count += side[0][j]
        }
        
        for (i in 1 until m) {
            for (j in 1 until n) {
                if (matrix[i][j] == 1) {
                    side[i][j] = 1 + minOf(side[i - 1][j], side[i][j - 1], side[i - 1][j - 1])
                    count += side[i][j]
                }
            }
        }
        return count
    }
}

空间优化

状态转移只与左、上、左上三个状态有关，不需要记录所有状态。

由于状态递推是从左到右遍历二维数组的，所以至少要存储一行的记录，否则要是只用三个变量记录上一个状态，换行从第1列开始递推的时候，你不知道左、上、左上的状态了。

但是一行缓存记录还不够，因为要读取左边和左上方的状态，在从左到右递推的时候，左上方的值被覆盖了，只能读取到左边的状态，所以要多记录上一行的状态，以便读取左上方的状态。

空间复杂度O(m)

如果m > n，按列遍历列表，跟按行遍历是一样的，可以做到O(n)空间复杂度，这里不再编写，形式相似。在n远小于m时这样做才有意义。

优化后代码（kotlin）

class Solution {
    fun countSquares(matrix: Array<IntArray>): Int {
        val m = matrix.size
        val n = matrix[0].size
        var count = 0
        val side = IntArray(n) { 0 }

        // 第一行
        for (j in 0 until n) {
            side[j] = if (matrix[0][j] == 1) 1 else 0
            count += side[j]
        }

        // 存储上一行状态，以便接下来读取左上方状态
        val pre = side.copyOf()
        
        for (i in 1 until m) {
            for (j in 0 until n) {
                side[j] = if (matrix[i][j] == 1) {
                    // side[j]: 上方状态
                    // side[j - 1]: 左方状态
                    // pre[j - 1]: 左上方状态
                    if (j == 0) 1 
                    else 1 + minOf(side[j], side[j - 1], pre[j - 1])
                } else 0
                count += side[j]
            }
            side.copyInto(pre)
        }
        return count
    }
}