统计全 1 子矩形 图解题解
这道题到底在问什么
- 输入
- mat=[[1,0,1],[1,1,0],[1,1,0]]
- 输出
- 13
- 输入
- mat=[[1,1],[1,1]]
- 输出
- 9
先想最直接的笨办法
这就是 3 行 3 列的矩阵,蓝色的是 0,相当于墙,其余是 1。第一步,挨个格子算它向左能连续接上几个 1,记成 g。规则很简单,格子本身是 0 就记 0;本身是 1,就看它左边那个格子的 g 是多少,再加 1。咱们从左上角一行一行、从左到右地算。（动画第 4 步）
最优解：一步一步想明白
- 3记住这两步:先把每个格子向左连续 1 的个数 g 算出来,再让每个格子当一次右下角,沿着它这一列往上扩,边扩边把这段行里 g 的最小值加进答案。下面先从算 g 开始。
- 4蓝格 = 0(墙),其余格要算出向左能连几个 1这就是 3 行 3 列的矩阵,蓝色的是 0,相当于墙,其余是 1。第一步,挨个格子算它向左能连续接上几个 1,记成 g。规则很简单,格子本身是 0 就记 0;本身是 1,就看它左边那个格子的 g 是多少,再加 1。咱们从左上角一行一行、从左到右地算。
- 5g = 1看格子 (0,0),它是 1,而且就在最左边一列,左边没有别人了,向左连续 1 只有它自己,g 记 1。
- 6本身是 0,g = 0看格子 (0,1),它本身就是 0,是一堵墙,向左根本接不上 1,直接记 g 等于 0。
- 7g = 1看格子 (0,2),它是 1。看它左边那个格子的 g 是 0,那从这里往左连续的 1 就是左边那串再加上自己,g 记 0 加 1,等于 1。
- 8g = 1看格子 (1,0),它是 1,而且就在最左边一列,左边没有别人了,向左连续 1 只有它自己,g 记 1。
- 9g = 2看格子 (1,1),它是 1。看它左边那个格子的 g 是 1,那从这里往左连续的 1 就是左边那串再加上自己,g 记 1 加 1,等于 2。
- 10本身是 0,g = 0看格子 (1,2),它本身就是 0,是一堵墙,向左根本接不上 1,直接记 g 等于 0。
- 11g = 1看格子 (2,0),它是 1,而且就在最左边一列,左边没有别人了,向左连续 1 只有它自己,g 记 1。
- 12g = 2看格子 (2,1),它是 1。看它左边那个格子的 g 是 1,那从这里往左连续的 1 就是左边那串再加上自己,g 记 1 加 1,等于 2。
- 13本身是 0,g = 0看格子 (2,2),它本身就是 0,是一堵墙,向左根本接不上 1,直接记 g 等于 0。
- 14g = 每格向左连续 1 的个数九个格子的 g 都算好了。第 0 行是 1、0、1,第 1 行是 1、2、0,第 2 行是 1、2、0。这里的 2 就表示这个格子向左能连上两个 1,也就是它自己加左边一个。有了这张 g 表,下一步就能数矩形了。
- 15橙 = 右下角,浅橙 = 正在扩的这一列若干行第二步开始数矩形。换个角度想:任何一个全 1 矩形,都有唯一一个右下角。于是咱们让每个格子轮流当一次右下角,把以它为右下角的矩形数清楚,加起来就不重不漏。具体怎么数,固定右下角这一列,从它本行开始往上扩,维护扩到的这些行里 g 的最小值 col,col 就是此刻能摆出的矩形宽度种数,每扩一行就把 col 加进答案。咱们一个格子一个格子来。
- 16这段最小 g = col = 1轮到格子 (0,0) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 1。
- 17本身是墙,贡献 0轮到格子 (0,1),它本身是 0,是一堵墙,以它收尾根本拼不出全是 1 的矩形,贡献 0,直接跳过,答案还是 1。
- 18这段最小 g = col = 1轮到格子 (0,2) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 2。
- 19这段最小 g = col = 1轮到格子 (1,0) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 3。
- 20这段最小 g = col = 1把上边界再往上抬一行,扩到第 0 行。现在这一段是第 0 行到第 1 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 1(刚才是 1),所以再添 1 种更高的矩形,加进答案,ans 变成 4。
- 21这段最小 g = col = 2轮到格子 (1,1) 当右下角。先只算它本行这一层,这一行它的 g 是 2,所以 col 等于 2,意思是只用这一行、右下角钉在这里,能摆出 2 种宽度的矩形,把 2 加进答案,ans 变成 6。
- 22撞到 0,这一列停继续往上扩到第 0 行,这一行在这一列是 0,是堵墙。col 取这段的最小值就被压成 0,说明再往上不可能全是 1 了,加 0 等于没加,这一列到此为止。格子 (1,1) 当右下角一共贡献到 ans 等于 6。
- 23本身是墙,贡献 0轮到格子 (1,2),它本身是 0,是一堵墙,以它收尾根本拼不出全是 1 的矩形,贡献 0,直接跳过,答案还是 6。
- 24这段最小 g = col = 1轮到格子 (2,0) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 7。
- 25这段最小 g = col = 1把上边界再往上抬一行,扩到第 1 行。现在这一段是第 1 行到第 2 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 1(刚才是 1),所以再添 1 种更高的矩形,加进答案,ans 变成 8。
- 26这段最小 g = col = 1把上边界再往上抬一行,扩到第 0 行。现在这一段是第 0 行到第 2 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 1(刚才是 1),所以再添 1 种更高的矩形,加进答案,ans 变成 9。
- 27这段最小 g = col = 2轮到格子 (2,1) 当右下角。先只算它本行这一层,这一行它的 g 是 2,所以 col 等于 2,意思是只用这一行、右下角钉在这里,能摆出 2 种宽度的矩形,把 2 加进答案,ans 变成 11。
- 28这段最小 g = col = 2把上边界再往上抬一行,扩到第 1 行。现在这一段是第 1 行到第 2 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 2(刚才是 2),所以再添 2 种更高的矩形,加进答案,ans 变成 13。
- 29撞到 0,这一列停继续往上扩到第 0 行,这一行在这一列是 0,是堵墙。col 取这段的最小值就被压成 0,说明再往上不可能全是 1 了,加 0 等于没加,这一列到此为止。格子 (2,1) 当右下角一共贡献到 ans 等于 13。
- 30本身是墙,贡献 0轮到格子 (2,2),它本身是 0,是一堵墙,以它收尾根本拼不出全是 1 的矩形,贡献 0,直接跳过,答案还是 13。
- 31所有右下角贡献之和 = 13九个格子都轮过一遍右下角了,把它们各自的贡献全加起来,正好是 13。这跟题面一开始数的 6 加 2 加 3 加 1 加 1 完全吻合。核心就是这两步:先算每格向左连续 1 的个数 g,再让每格当右下角向上扩、累加这段 g 的最小值。
⚠️ 容易写错的地方
✗ 错：直接枚举上下左右四条边界去判矩形
✓ 对：换成按右下角计数,每格往上扩累加 col
四重枚举再加判全 1 会非常慢,按右下角加 g 最小值的数法把重复劳动省掉了
✗ 错：往上扩时只看当前行的 g,不取最小值
✓ 对：col 必须是扩到的这一段所有行里 g 的最小值
矩形要每一行都全 1,宽度被最窄的那一行卡住,所以只能取这段的最小宽度
✗ 错：g 等于 0 的格子还硬当右下角去数
✓ 对：它本身是墙,贡献 0,应当跳过
右下角自己都不是 1,不可能围出全 1 矩形
✗ 错：担心同一个矩形被数到两次
✓ 对：每个矩形的右下角唯一,按右下角分类天然不重复
一个矩形只有一个右下角,所以让每格当一次右下角,加起来既不重也不漏
完整代码（Python / C++ / Java）
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 ansC++
#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;
}
}复杂度
时间
O(m² · n)
m 是行数 n 是列数。填 g 表是 O(m·n)。数矩形时,每个右下角最坏要往上扫 m 行,一共 m·n 个右下角,所以是 O(m·n·m),即 O(m²·n)。C++ 和 Java 用 col 大于 0 提前跳出能剪掉不少,但最坏情况(整片全是 1)仍是这个量级
空间
O(m · n)
主要开销是那张 g 表,要存下每个格子的值,峰值是 O(m·n)。向上扩时只用了 col 这一个额外变量,是 O(1),不影响整体,所以空间按峰值是 O(m·n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计全 1 子矩形 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么以每格为右下角向上扩,累加 col,就能不重不漏地数出所有矩形?+
关键在右下角唯一。任何一个全 1 子矩形,它最右下那个格子是确定的、独一份。所以咱们让每个格子轮流当一次右下角,只数右下角恰好钉在它身上的那些矩形,不同格子数到的矩形互不相同,加起来既不会重复也不会漏。而以某格为右下角的矩形,无非是上边界从本行往上抬、左边界由宽度决定,往上扩到第 k 行时,这段里 g 的最小值就是合法宽度的种数,把每一层的 col 加起来,正好是以它为右下角的全部矩形数。
这个 O(m 平方乘 n) 还能再快吗?+
能,但要换个方向:不用向左的 g,改成给每一列算一个向上连续 1 的高度 height,也就是从当前行往上数,这一列能接连几个 1。这样把每一行看成一排柱子的直方图,数以这一行为底边的全 1 矩形,就是经典的直方图数矩形,可以用单调栈,一边扫一边维护一个递推量,把每一行的处理压到线性,整体做到 O(m 乘 n)。思路是当新柱子比栈顶矮时弹栈,用前一个更矮的位置去更新当前列能贡献的矩形数。实现稍复杂,但量级更优,面试里能说出这个方向是加分项。
空间上一定要存整张 g 表吗?+
本题这版向上扩时要回看上面每一行的 g,所以保留了整张 m 乘 n 的表。如果改用刚才说的单调栈按行推进,每处理一行只需要上一行的若干信息,可以把空间压到 O(n) 这个量级,一行一行滚动着算,不必把整张表都留在内存里。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计全 1 子矩形 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。