Medium

题目描述

给你一个 m x n 的二进制矩阵 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。

提示：

  • 1 <= m, n <= 150
  • mat[i][j] 是 0 或 1

解题思路

这道题需要统计所有元素都为1的子矩形数量。我们可以使用动态规划的思想来解决。

核心思路：

  1. 对于每一行，我们预处理出每个位置向左连续1的个数
  2. 然后对于每个位置作为右下角，枚举所有可能的上边界
  3. 在枚举上边界的过程中，维护当前矩形的宽度（即所有行中向左连续1的最小值）

具体步骤：

  1. 预处理：对于每一行 i 的每个位置 j，计算 height[i][j] 表示从位置 (i,j) 向左连续1的个数
  2. 枚举右下角：对于每个位置 (i,j) 作为矩形的右下角
  3. 枚举上边界：从当前行向上枚举，维护矩形的最小宽度
  4. 累加结果：每确定一个上边界，就能形成若干个宽度递减的矩形

这种方法的时间复杂度是 O(m²n)，对于给定的约束条件是可以接受的。通过逐行向上扩展并维护最小宽度，我们能够高效地计算出所有可能的子矩形数量。

代码实现

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> height(m, vector<int>(n, 0));
        
        // 预处理：计算每个位置向左连续1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    height[i][j] = (j == 0) ? 1 : height[i][j-1] + 1;
                }
            }
        }
        
        int result = 0;
        // 枚举每个位置作为右下角
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    int minWidth = height[i][j];
                    // 向上枚举上边界
                    for (int k = i; k >= 0 && mat[k][j] == 1; k--) {
                        minWidth = min(minWidth, height[k][j]);
                        result += minWidth;
                    }
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        height = [[0] * n for _ in range(m)]
        
        # 预处理：计算每个位置向左连续1的个数
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    height[i][j] = 1 if j == 0 else height[i][j-1] + 1
        
        result = 0
        # 枚举每个位置作为右下角
        for i in range(m):
            for j in range(n):
                if mat[i][j] == 1:
                    min_width = height[i][j]
                    # 向上枚举上边界
                    k = i
                    while k >= 0 and mat[k][j] == 1:
                        min_width = min(min_width, height[k][j])
                        result += min_width
                        k -= 1
        
        return result

public class Solution {
    public int NumSubmat(int[][] mat) {
        int m = mat.Length, n = mat[0].Length;
        int[][] height = new int[m][];
        for (int i = 0; i < m; i++) {
            height[i] = new int[n];
        }
        
        // 预处理：计算每个位置向左连续1的个数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    height[i][j] = (j == 0) ? 1 : height[i][j-1] + 1;
                }
            }
        }
        
        int result = 0;
        // 枚举每个位置作为右下角
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 1) {
                    int minWidth = height[i][j];
                    // 向上枚举上边界
                    for (int k = i; k >= 0 && mat[k][j] == 1; k--) {
                        minWidth = Math.Min(minWidth, height[k][j]);
                        result += minWidth;
                    }
                }
            }
        }
        
        return result;
    }
}

var numSubmat = function(mat) {
    const m = mat.length;
    const n = mat[0].length;
    let count = 0;
    
    // For each row, calculate heights of consecutive 1s ending at current row
    const heights = new Array(n).fill(0);
    
    for (let i = 0; i < m; i++) {
        // Update heights for current row
        for (let j = 0; j < n; j++) {
            heights[j] = mat[i][j] === 1 ? heights[j] + 1 : 0;
        }
        
        // For each column as starting point, count submatrices
        for (let j = 0; j < n; j++) {
            let minHeight = heights[j];
            for (let k = j; k < n; k++) {
                minHeight = Math.min(minHeight, heights[k]);
                if (minHeight === 0) break;
                count += minHeight;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m²n)，其中 m 是矩阵的行数，n 是矩阵的列数。预处理需要 O(mn)，主循环中对每个位置向上枚举最多 m 个位置
空间复杂度O(mn)，需要额外的二维数组存储每个位置向左连续1的个数

相关题目