题目大意：
统计全 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1504
解题思路分析：
我们之前讲过一道类似的题目，LEETCODE 1277. Count Square Submatrices with All Ones 解题思路分析，那一题统计的是正方形，而本题统计的是矩形，两者本质上没用区别。与上一题同理，我们可以采用DP动态规划或者前缀和的方式解题。本题我们以前缀和方式为例。
- 首先我们对矩阵进行数据初始化。即求出每一行以及每一列上的前缀和。
- 遍历矩阵每一个点（两层循环），并以该点最为起点（row, col），向右下方向画矩形（两层循环，分别循环矩形的宽width和高height），注意矩形范围不能越界。起始时width和height分别为0，即当前点自身是一个矩形。
- 当width扩大一格后，实际上是增加了(row, col+width)到(row+height, col+width)这一部分的面积（宽为1，高为height），我们通过前缀和数组求出该区域和是否等于height，如果等于，返回结果加一即可。
- height扩大一格的操作同理。
实现代码：
public int numSubmat(int[][] mat) {
int[][] preSumRow=new int[mat.length][mat[0].length]; // 每一行前缀和
int[][] preSumCol=new int[mat[0].length][mat.length]; // 每一列前缀和
for(int r=0;r<mat.length;r++){
for(int c=0;c<mat[0].length;c++){
if(c==0) preSumRow[r][c]=mat[r][c];
else preSumRow[r][c]=preSumRow[r][c-1]+mat[r][c];
}
}
for(int c=0;c<mat[0].length;c++){
for(int r=0;r<mat.length;r++){
if(r==0) preSumCol[c][r]=mat[r][c];
else preSumCol[c][r]=preSumCol[c][r-1]+mat[r][c];
}
}
int res=0;
for(int r=0;r<mat.length;r++){ // 循环每一点
for(int c=0;c<mat[0].length;c++){
for(int rl=0;rl+r<mat.length;rl++){ // 以当前点为顶点，向下扩大一格
for(int cl=0;cl+c<mat[0].length;cl++){ // 以当前点为顶点，向右扩大一格
int row=r+rl,col=c+cl;
// 通过前缀和数组求出新增区域面积，如果该面积与新增面积相同，代表区域内都是1
if((c==0&&preSumRow[row][col]==cl+1||c>0&&preSumRow[row][col]-preSumRow[row][c-1]==cl+1)
&&(r==0&&preSumCol[col][row]==rl+1||r>0&&preSumCol[col][row]-preSumCol[col][r-1]==rl+1)){
res++; // 返回结果加一
}else{
break;
}
}
}
}
}
return res;
}本题解法执行时间为80ms。
Runtime: 80 ms, faster than 16.67% of Java online submissions for Count Submatrices With All Ones.
Memory Usage: 39.8 MB, less than 100.00% of Java online submissions for Count Submatrices With All Ones.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1504-count-submatrices-with-all-ones-解题思路分析/