我要评论
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 <= 1501 <= columns <= 1500 <= 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
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论