leetcode1504. 统计全 1 子矩形（Python3）

leetcode1504. 统计全 1 子矩形

给你一个只包含 0 和 1 的 rows * columns 矩阵 mat ，请你返回有多少个 子矩形 的元素全部都是 1 。

示例 1：

输入：mat = [[1,0,1],
            [1,1,0],
            [1,1,0]]
输出：13
解释：
有 6 个 1x1 的矩形。
有 2 个 1x2 的矩形。
有 3 个 2x1 的矩形。
有 1 个 2x2 的矩形。
有 1 个 3x1 的矩形。
矩形数目总共 = 6 + 2 + 3 + 1 + 1 = 13 。

示例 2：

输入：mat = [[0,1,1,0],
            [0,1,1,1],
            [1,1,1,0]]
输出：24
解释：
有 8 个 1x1 的子矩形。
有 5 个 1x2 的子矩形。
有 2 个 1x3 的子矩形。
有 4 个 2x1 的子矩形。
有 2 个 2x2 的子矩形。
有 2 个 3x1 的子矩形。
有 1 个 3x2 的子矩形。
矩形数目总共 = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24 。

示例 3：

输入：mat = [[1,1,1,1,1,1]]
输出：21

示例 4：

输入：mat = [[1,0,1],[0,1,0],[1,0,1]]
输出：5

提示：

• 1 <= rows <= 150
• 1 <= columns <= 150
• 0 <= mat[i][j] <= 1

---

方法：动态规划

思路：

本题的暴力思路就是枚举所有的矩形（左上角坐标和右下角坐标），然后计算这个矩形内是不是都为1；但是这样枚举的时间复杂度就是O(N ^ 4)，计算矩形内部是不是都为1最多需要O(N ^ 2)，有太多的重复计算，我们需要使用动态规划来解决。

我们设dp数组为二维，dp(i,j)表示(i,j)这个点（包括该点）该行左边连续的1的个数。我们计算这个的目的是这样的，如果以(i,j)为矩形的右下角，那么高为1的那满足条件的矩形个数就为dp(i,j)，如下图所示：

我们计算出所有的dp之后，我们使用两层循环来遍历所有的点，计算以这个点为右下角的矩形有多少个。以该点(i,j)为例，以(i,j)为右下角，高度为1的矩形个数为dp(i,j)；我们还需要向上遍历，来计算以该点(i,j)为右下角，高度为2、3、4…的矩形有多少个。

当遍历到上一行时，dp(i-1,j)表示(i-1,j)左边连续1的个数，因为要构成两层的矩形，矩形中都为1；所以可以构成的矩形的数量为：min(dp(i,j),dp(i-1,j))，我们维护这个数，这个数表示这两层共有的都为1的宽度，继续向上遍历，更新这个宽度，找到高度为3、4、5…的矩形。

遍历所有的位置，计算它为右下角的矩形个数，返回总数。

代码：

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])
        dp = [[0 for _ in range(cols)] for _ in range(rows)]
        #dp[i][j]表示第i行，从j开始往左数连续有多少个1
        for i in range(rows):
            for j in range(cols):
                if mat[i][j]:
                    dp[i][j] = dp[i][j-1] + 1 if j > 0 else 1
        res = 0
        #遍历每个位置，以这个位置为矩形右下角
        for i in range(rows):
            for j in range(cols):
                #leftnum维护可以构成矩形的最大宽度
                leftnum = float('inf')
                #从(i,j)开始向上遍历，对于第i行，求出dp(i,j)表示(i,j)左边的连续1个数
                #也就是以(i,j)为右下角，高为1，的矩形个数(一个长度对应一个矩形)
                #遍历到i-1行的时候，更新leftnum，表示第i行和第i-1行从j往左的连续1的个数的
                #较小值，这就是以(i,j)为右下角，高为2的矩形个数
                #遍历i上面的所有行，找到所有的(i,j)为右下角，高度分别为1,2,3...，i+1的矩形
                for k in range(i,-1,-1):
                    leftnum = min(leftnum,dp[k][j])
                    #如果某一行更新后，leftnum为0，那么上面的行就不用看了，break跳出
                    if leftnum == 0:
                        break
                    res += leftnum
        return res

结果：

本文地址：https://blog.csdn.net/weixin_43422466/article/details/107158319