1504. 统计全 1 子矩形

 

class Solution {

    public int numSubmat(int[][] mat) {
        if(mat.length == 0 || mat[0].length == 0) return 0;
        int m = mat.length, n = mat[0].length;
        int[][] dp = new int[m][n]; //计算i，j位置左边连续1的个数
        for(int i = 0; i < m; i++) {
            int len = 0;
            for(int j = 0; j < n; j++) {
                if(mat[i][j] == 1) len++;
                else len = 0;
                dp[i][j] = len;
            }
        }
        int res = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                int min = m * n; // 逐层向上累加子矩形
                for(int k = i; k >= 0; k--) {
                    min = Math.min(dp[k][j],min);
                    if(min == 0) break;
                    res += min;
                }
            }
        }
        return res;
    }
}