统计全 1 子矩形 图解题解

统计全 1 子矩形，到底在数什么

给一个只含 0 和 1 的矩阵，记它 m 行 n 列，问能圈出多少个全是 1 的子矩形。子矩形不限正方形，横条、竖条、大方块、单格都算。题面 mat=[[1,0,1],[1,1,0],[1,1,0]] 答案 13。

四条边界一起枚举为什么慢到不能用

一个子矩形由上下左右四条边界钉死，枚举所有边界组合逐个验证，各边界有 O(m) 或 O(n) 种选法，光矩形就有 O(m²·n²) 个（大 O 记号，描述矩阵变大时操作数怎么涨），稍大就跑不完。

先给每格记它向左连续几个 1

突破口是给每格记一个数 g：它往左连续的 1 有几个（含自己）。用 (i,j) 表示第 i 行第 j 列那格（行在前列在后，从 0 起）。本身是 0 就 g 记 0；是 1 就取左邻的 g 加 1。这是一维动态规划（DP）。

拿第 0 行 [1,0,1] 走一遍：(0,0) 在最左列 g 记 1；(0,1) 是 0 记 0；(0,2) 左邻 g 是 0 记 1。第 1 行的 (1,1) 左邻 g 是 1 记 2——即向左连上两个 1（自己加左边一个）。

为什么让每格当右下角、往上扩取最小 g

有了 g 表，抓住一点：任何全 1 矩形都有唯一的右下角。让每格轮流当右下角，把以它收尾的矩形数清、加起来不重不漏。

固定右下角 (i,j)，沿第 j 列从第 i 行往上抬。只用本行时，矩形右边贴 (i,j)、宽度 1 到 g[i][j]，共 g[i][j] 种。往上抬一行，圈的是高两行、右下角仍 (i,j) 的矩形；两行都要全 1，宽度只能取两行 g 更小的，迁就最窄那行。所以 col 取扩到的行里 g 的最小值，每抬一行把 col 累加进答案。某行这列是 0 时 col 压 0，再往上不全 1，这列打住。

拿题面 3 乘 3 矩阵亲手数一遍

g 表填好：第 0 行 [1,0,1]、第 1、2 行都是 [1,2,0]。九格轮流当右下角。(0,0) 本行加 1，ans 到 1；(0,1) 是 0 跳过；(0,2) 加 1 到 2。(1,0) 本行加 1 到 3，往上扩一行 g 仍 1 加 1 到 4。

(1,1) 本行加 2 到 6，往上遇 0 停。(2,0) 本行 g 是 1 加 1 到 7；往上扩到第 1 行、两行 g 都是 1 加 1 到 8，再扩到第 0 行、三行 g 都是 1 加 1 到 9。(2,1) 本行加 2 到 11，往上扩一行最小是 2 再加 2 到 13，遇 0 停。其余 0 格跳过，ans=13，和题面对上。

往上扩时照搬本行的 g、忘了取最小，多出的矩形从哪冒出来

往上抬每高一行，宽度必须压到这段最窄的 g；一直用本行的 g，就把上面不够宽处也当铺满，数出不全 1 的假矩形，答案偏大。另一个错是拿 g 为 0 的格当右下角累加——它是墙，拼不出全 1 矩形，得跳过。

复杂度：填 g 表 O(m·n)；数矩形时每个右下角最坏往上扫一整列、共 m·n 个，是 O(m²·n)。空间主要是 g 表 O(m·n)。边界：全 0 答案 0；一行 [1,0,1] 两个 1 各贡献一个单格、共 2。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numSubmat(self, mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        g = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if mat[i][j]:
                    g[i][j] = 1 if j == 0 else 1 + g[i][j - 1]
        ans = 0
        for i in range(m):
            for j in range(n):
                col = inf
                for k in range(i, -1, -1):
                    col = min(col, g[k][j])
                    ans += col
        return ans

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> g(m, vector<int>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    g[i][j] = j == 0 ? 1 : 1 + g[i][j - 1];
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int col = 1 << 30;
                for (int k = i; k >= 0 && col > 0; --k) {
                    col = min(col, g[k][j]);
                    ans += col;
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length, n = mat[0].length;
        int[][] g = new int[m][n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (mat[i][j] == 1) {
                    g[i][j] = j == 0 ? 1 : 1 + g[i][j - 1];
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                int col = 1 << 30;
                for (int k = i; k >= 0 && col > 0; --k) {
                    col = Math.min(col, g[k][j]);
                    ans += col;
                }
            }
        }
        return ans;
    }
}