统计全为1的正方形子矩阵

0x1 题目详情

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

测试用例:

输入：matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] 输出：15 解释： 边长为 1 的正方形有 10 个。 边长为 2 的正方形有 4 个。 边长为 3 的正方形有 1 个。 正方形的总数 = 10 + 4 + 1 = 15.

0x2 解题思路

一看到这道题，我立马想起来以前做过的一道题，在一个m*n的矩形中，找到由1构成的最大正方形的边长。跟这道题神似。那道题是用动态规划。虽然我不知道状态状态转移方程咋写出来的。但是这道题仍然可以使用求最大正方形边长的思路。

求一个矩阵中由1构成的最大正方形时：我们需要求出每个位置上所能构成的最大正方形，我们可以已当前求的位置作为正方形的右下角，来看看在右下角固定时，该位置能够构成的正方形最多有多大。

这时，能够构成的最大正方形由固定位置的左边、上边和左上角的最大正方形决定。这里可能有点抽象。在下图中，我们将固定的右下角分配为橘色。左边分配为蓝色，上边分配为绿色，左上角分配为黄色。(注意上述中所有的正方形都是在右下角固定时求来的)。

如果你看懂了如何求最大正方形边长，那么这道题肯定不会难住你。一个位置能够的子矩阵数量不就等于构成的最大正方形边长吗？没有任何转换，只要在求边长的过程中统计最大边长和就行啦。

0x3 代码实现

知道了状态转移方程，写代码就非常简单了。

$dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][]j),dp[i-1][]j-1)$

时间复杂为$O(MN)$,空间复杂度为$O(MN)$，当然空间这里仍有优化的空间。

class Solution {
public int countSquares(int[][] matrix) {
    if(matrix.length==0 || matrix[0].length==0){
        return 0;
    }
    int[][] dp=new int[matrix.length+1][matrix[0].length+1];
    int result=0;
    for(int i=1;i<dp.length;i++){
        for(int j=1;j<dp[0].length;j++){
            if(matrix[i-1][j-1]==0){
                dp[i][j]=0;
            }
            else{
                dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
            }
            if(dp[i][j]>0){
                result+=dp[i][j];
            }
        }
    }
    return result;
}
}

0x4 课后总结

我觉得吧，这个状态转义方程全靠规律总结出来的，我一般都是先写递归，然后再改成dp，这种方式简直无脑，后续遇到相关的题目我会介绍的奥。至于我为什么把它分到几何题呢，因为求最大正方形这一类题目都可以靠最大边长这个方式解...