LeetCode.221.最大正方形（中等）

题目

LeetCode.221.最大正方形（中等）

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

题解

最值问题考虑用动态规划。
想办法把大问题划分子问题+有限步骤。

从基本情况出发

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

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

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

而这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 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[i][j]，再求平方就是最终结果

复杂度

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

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

        side[0][0] = if (matrix[0][0] == '1') 1 else 0
        maxLength = maxOf(maxLength, side[0][0])

        for (i in 1 until m) {
            side[i][0] = if (matrix[i][0] == '1') 1 else 0
            maxLength = maxOf(maxLength, side[i][0])
        }

        for (j in 1 until n) {
            side[0][j] = if (matrix[0][j] == '1') 1 else 0
            maxLength = maxOf(maxLength, 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])
                    maxLength = maxOf(maxLength, side[i][j])
                }
            }
        }
        
        return maxLength * maxLength
    }
}

空间优化

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

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

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

空间复杂度O(m)

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

优化的代码

class Solution {
    fun maximalSquare(matrix: Array<CharArray>): Int {
        val m = matrix.size
        val n = matrix[0].size
        val side = IntArray(n) { 0 }
        var maxLength = 0
        
        // 第一行状态
        for (j in 0 until n) {
            side[j] = if (matrix[0][j] == '1') 1 else 0
            maxLength = maxOf(maxLength, side[j])
        }

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