题目描述
思路解析动画文字版
记住这两步:先把每个格子向左连续 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题