cpp 解法, 执行用时: 56 ms, 内存消耗: 14.8 MB, 提交时间: 2022-12-01 23:54:31

/**
 * 矩阵里每个点(i, j)统计他这行左边到他这个位置最多有几个连续的1，存为left[i][j]。
 * 然后对于每个点(i, j)，我们固定子矩形的右下角为(i, j)，利用left从该行i向上寻找子矩阵左上角为第k行的矩阵个数。
 * 每次将子矩阵个数加到答案中即可
 **/
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size();
        int m = mat[0].size();
        vector<vector<int> > left(n,vector<int>(m));
        int now = 0;
        for(int i=0;i<n;i++){
            now = 0;
            for(int j=0;j<m;j++){
                if(mat[i][j] == 1) now ++;
                else now = 0;
                left[i][j] = now;
            }
        }
        int ans = 0,minx;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                minx = 0x3f3f3f3f;
                for(int k=i;k>=0;k--){
                    minx = min(left[k][j],minx);
                    ans += minx;
                }
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 124 ms, 内存消耗: 15.7 MB, 提交时间: 2022-12-01 23:52:32

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        
        row = [[0] * m for _ in range(n)]
        for i in range(n):
            for j in range(m):
                if j == 0:
                    row[i][j] = mat[i][j]
                else:
                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1
        
        ans = 0
        for j in range(m):
            Q = list()
            total = 0
            for i in range(n):
                height = 1
                while Q and Q[-1][0] > row[i][j]:
                    # 弹出的时候要减去多于的答案
                    total -= Q[-1][1] * (Q[-1][0] - row[i][j])
                    height += Q[-1][1]
                    Q.pop()
                total += row[i][j]
                ans += total
                Q.append((row[i][j], height))

        return ans

java 解法, 执行用时: 13 ms, 内存消耗: 42.1 MB, 提交时间: 2022-12-01 23:51:30

class Solution {
    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] row = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j == 0) {
                    row[i][j] = mat[i][j];
                } else if (mat[i][j] != 0) {
                    row[i][j] = row[i][j - 1] + 1;
                } else {
                    row[i][j] = 0;
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < m; ++j) { 
            int i = 0;
            Deque<int[]> Q = new LinkedList<int[]>();
            int sum = 0; 
            while (i <= n - 1) { 
                int height = 1; 
                while (!Q.isEmpty() && Q.peekFirst()[0] > row[i][j]) {
                  	// 弹出的时候要减去多于的答案
                    sum -= Q.peekFirst()[1] * (Q.peekFirst()[0] - row[i][j]); 
                    height += Q.peekFirst()[1]; 
                    Q.pollFirst(); 
                } 
                sum += row[i][j]; 
                ans += sum; 
                Q.offerFirst(new int[]{row[i][j], height}); 
                i++; 
            } 
        } 
        return ans;
    }
}

java 解法, 执行用时: 6 ms, 内存消耗: 42.2 MB, 提交时间: 2022-12-01 23:51:14

class Solution {
    public int numSubmat(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] row = new int[n][m];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (j == 0) {
                    row[i][j] = mat[i][j];
                } else if (mat[i][j] != 0) {
                    row[i][j] = row[i][j - 1] + 1;
                } else {
                    row[i][j] = 0;
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                int col = row[i][j];
                for (int k = i; k >= 0 && col != 0; --k) {
                    col = Math.min(col, row[k][j]);
                    ans += col;
                }
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 632 ms, 内存消耗: 15.5 MB, 提交时间: 2022-12-01 23:50:59

class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        n, m = len(mat), len(mat[0])
        
        row = [[0] * m for _ in range(n)]  # (i, j) 为右下角，向左延伸1的个数
        for i in range(n):
            for j in range(m):
                if j == 0:
                    row[i][j] = mat[i][j]  
                else:
                    row[i][j] = 0 if mat[i][j] == 0 else row[i][j - 1] + 1
        
        ans = 0
        for i in range(n):
            for j in range(m):
                col = row[i][j]
                for k in range(i, -1, -1):  # 第 k 行到第 i 行「每一行第 j 列向左延伸连续 1 的个数」
                    col = min(col, row[k][j]) 
                    if col == 0:
                        break
                    ans += col
        
        return ans