题目

5454. 统计全 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

本题是7月5号周赛第三题，比赛时完全没有思路。赛后参考其他大神的题解才理解。下面说一下现在的理解。

题目说找全1的子矩阵，也就是统计在确定的边界之内的数字是否都为1。

1. 对于矩阵题目通常可以考虑确定两个边界来简化题目。假设矩阵为 n * m，对于给定的上下边界row_low和row_hight(此时矩阵高度为row_hight - row_low + 1，假设索引从0开始)，然后我们从0 -> m开始遍历column。因为row会覆盖所有的行，所有我们固定row后，只需要考虑column。如图
   image.png
2. 对于给定高度，遍历column，当所在列全部为1是，矩形为符合要求的子矩形；否则不符合要求。假设row_low = 1, row_high=2。
   1- col=0此时高度为2的矩形有1个(cnt=1)，更新ans里；当col从0->1时高度为row_high - row_low + 1的矩形有3个(1, 0) -> (2, 0),(1, 1) -> (2, 2), (1, 0) -> (2, 2)，col从0变为1贡献了2个矩形(cnt++)，累加到ans里；当col从1->2贡献3个矩形(cnt++)，可以总结当col从m->m+1切col全部为1时贡献cnt++个矩形，累加到ans里。
   2- 当col对于的数字不全为1时，则需要重置cnt=0，因为在给定的row_low, row_high以及col无法形成新的子矩形。继续遍历col，重复2.1步骤。
3. 为了方便判断2.1和2.2的条件可以添加一个sum数组辅助判断。
   最后给出Java代码：

public int numSubmat(int[][] mat) {
    int n = mat.length;
    int m = mat[0].length;
    int[] sum = new int[m], int ans = 0;
    for (int i = 0; i < n; i++) {
        Arrays.fill(sum, 0);  // 每次i变更是需要重置sum，因为此时sum里面的值不可用了
        for (int j = i; j < n; j++) {
            for (int k = 0; k < m; k++) {
                sum[k] += mat[j][k]; // j每迭代一次更新一下sum[k]，如图中当i=1&j=1是将第1行更新到sum中；当j=2是将第2行迭代至sum中
            }
            int cnt = 0, high = j - i + 1;
            for (int k = 0; k < m; k++) {
                if (sum[k] == high) {
                    cnt++;
                    ans += cnt;
                } else {
                    cnt = 0;
                }
            }
        }
    }
    return ans;
}