题目描述
思路解析
一句话答案：LeetCode 1504 统计全 1 子矩形：先给每格算向左连续 1 的个数 g，再让每格当一次右下角、沿列往上扩，把这段行里 g 的最小值累加进答案，右下角唯一保证不重不漏。时间 O(m²·n)、空间 O(m·n)。
统计全 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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这两步:先把每个格子向左连续 1 的个数 g 算出来,再让每个格子当一次右下角,沿着它这一列往上扩,边扩边把这段行里 g 的最小值加进答案。下面先从算 g 开始。
阶段一 · 算每格向左连续 1 的个数 g：这就是 3 行 3 列的矩阵,蓝色的是 0,相当于墙,其余是 1。第一步,挨个格子算它向左能连续接上几个 1,记成 g。规则很简单,格子本身是 0 就记 0;本身是 1,就看它左边那个格子的 g 是多少,再加 1。咱们从左上角一行一行、从左到右地算。
算 g · 格子 (0,0) → 1：看格子 (0,0),它是 1,而且就在最左边一列,左边没有别人了,向左连续 1 只有它自己,g 记 1。
算 g · 格子 (0,1) → 0：看格子 (0,1),它本身就是 0,是一堵墙,向左根本接不上 1,直接记 g 等于 0。
算 g · 格子 (0,2) → 1：看格子 (0,2),它是 1。看它左边那个格子的 g 是 0,那从这里往左连续的 1 就是左边那串再加上自己,g 记 0 加 1,等于 1。
算 g · 格子 (1,0) → 1：看格子 (1,0),它是 1,而且就在最左边一列,左边没有别人了,向左连续 1 只有它自己,g 记 1。
算 g · 格子 (1,1) → 2：看格子 (1,1),它是 1。看它左边那个格子的 g 是 1,那从这里往左连续的 1 就是左边那串再加上自己,g 记 1 加 1,等于 2。
算 g · 格子 (1,2) → 0：看格子 (1,2),它本身就是 0,是一堵墙,向左根本接不上 1,直接记 g 等于 0。
算 g · 格子 (2,0) → 1：看格子 (2,0),它是 1,而且就在最左边一列,左边没有别人了,向左连续 1 只有它自己,g 记 1。
算 g · 格子 (2,1) → 2：看格子 (2,1),它是 1。看它左边那个格子的 g 是 1,那从这里往左连续的 1 就是左边那串再加上自己,g 记 1 加 1,等于 2。
算 g · 格子 (2,2) → 0：看格子 (2,2),它本身就是 0,是一堵墙,向左根本接不上 1,直接记 g 等于 0。
阶段一完成 · g 全算好了：九个格子的 g 都算好了。第 0 行是 1、0、1,第 1 行是 1、2、0,第 2 行是 1、2、0。这里的 2 就表示这个格子向左能连上两个 1,也就是它自己加左边一个。有了这张 g 表,下一步就能数矩形了。
阶段二 · 每个格子当右下角,沿这一列向上扩：第二步开始数矩形。换个角度想:任何一个全 1 矩形,都有唯一一个右下角。于是咱们让每个格子轮流当一次右下角,把以它为右下角的矩形数清楚,加起来就不重不漏。具体怎么数,固定右下角这一列,从它本行开始往上扩,维护扩到的这些行里 g 的最小值 col,col 就是此刻能摆出的矩形宽度种数,每扩一行就把 col 加进答案。咱们一个格子一个格子来。
右下角 (0,0) · 上扩到第 0 行 · col=1：轮到格子 (0,0) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 1。
右下角 (0,1) · 是 0,跳过：轮到格子 (0,1),它本身是 0,是一堵墙,以它收尾根本拼不出全是 1 的矩形,贡献 0,直接跳过,答案还是 1。
右下角 (0,2) · 上扩到第 0 行 · col=1：轮到格子 (0,2) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 2。
右下角 (1,0) · 上扩到第 1 行 · col=1：轮到格子 (1,0) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 3。
右下角 (1,0) · 上扩到第 0 行 · col=1：把上边界再往上抬一行,扩到第 0 行。现在这一段是第 0 行到第 1 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 1(刚才是 1),所以再添 1 种更高的矩形,加进答案,ans 变成 4。
右下角 (1,1) · 上扩到第 1 行 · col=2：轮到格子 (1,1) 当右下角。先只算它本行这一层,这一行它的 g 是 2,所以 col 等于 2,意思是只用这一行、右下角钉在这里,能摆出 2 种宽度的矩形,把 2 加进答案,ans 变成 6。
右下角 (1,1) · 上扩到第 0 行 · col=0：继续往上扩到第 0 行,这一行在这一列是 0,是堵墙。col 取这段的最小值就被压成 0,说明再往上不可能全是 1 了,加 0 等于没加,这一列到此为止。格子 (1,1) 当右下角一共贡献到 ans 等于 6。
右下角 (1,2) · 是 0,跳过：轮到格子 (1,2),它本身是 0,是一堵墙,以它收尾根本拼不出全是 1 的矩形,贡献 0,直接跳过,答案还是 6。
右下角 (2,0) · 上扩到第 2 行 · col=1：轮到格子 (2,0) 当右下角。先只算它本行这一层,这一行它的 g 是 1,所以 col 等于 1,意思是只用这一行、右下角钉在这里,能摆出 1 种宽度的矩形,把 1 加进答案,ans 变成 7。
右下角 (2,0) · 上扩到第 1 行 · col=1：把上边界再往上抬一行,扩到第 1 行。现在这一段是第 1 行到第 2 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 1(刚才是 1),所以再添 1 种更高的矩形,加进答案,ans 变成 8。
右下角 (2,0) · 上扩到第 0 行 · col=1：把上边界再往上抬一行,扩到第 0 行。现在这一段是第 0 行到第 2 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 1(刚才是 1),所以再添 1 种更高的矩形,加进答案,ans 变成 9。
右下角 (2,1) · 上扩到第 2 行 · col=2：轮到格子 (2,1) 当右下角。先只算它本行这一层,这一行它的 g 是 2,所以 col 等于 2,意思是只用这一行、右下角钉在这里,能摆出 2 种宽度的矩形,把 2 加进答案,ans 变成 11。
右下角 (2,1) · 上扩到第 1 行 · col=2：把上边界再往上抬一行,扩到第 1 行。现在这一段是第 1 行到第 2 行,要让矩形每一行都全 1,宽度得迁就最窄的那行。这段里 g 的最小值是 2(刚才是 2),所以再添 2 种更高的矩形,加进答案,ans 变成 13。
右下角 (2,1) · 上扩到第 0 行 · col=0：继续往上扩到第 0 行,这一行在这一列是 0,是堵墙。col 取这段的最小值就被压成 0,说明再往上不可能全是 1 了,加 0 等于没加,这一列到此为止。格子 (2,1) 当右下角一共贡献到 ans 等于 13。
右下角 (2,2) · 是 0,跳过：轮到格子 (2,2),它本身是 0,是一堵墙,以它收尾根本拼不出全是 1 的矩形,贡献 0,直接跳过,答案还是 13。
答案 · 13 个全 1 子矩形：九个格子都轮过一遍右下角了,把它们各自的贡献全加起来,正好是 13。这跟题面一开始数的 6 加 2 加 3 加 1 加 1 完全吻合。核心就是这两步:先算每格向左连续 1 的个数 g,再让每格当右下角向上扩、累加这段 g 的最小值。
边界想清:全是 0 答案为 0;单行 1、0、1 时两个 1 各贡献一个单格共 2(连续 1 段长 L 则贡献 L 乘以括号 L 加 1 括号 再除以 2);单列三个 1 时三个右下角分别贡献 1、2、3,共 6。
面试重点:右下角唯一保证不重不漏、改用每列向上高度 height 后每行是直方图数矩形可用单调栈优化到 O(m 乘 n)、按行滚动可把空间压到 O(n)。
参考代码
from __future__ import annotationsfrom 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复杂度
- 时间：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)
易错点
面试追问把动画讲成自己的话
追问为什么以每格为右下角向上扩,累加 col,就能不重不漏地数出所有矩形?
追问这个 O(m 平方乘 n) 还能再快吗?
追问空间上一定要存整张 g 表吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
和为奇数的子数组数目
LeetCode 1524 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题