题目描述
思路解析动画文字版
记住这两步:先把每格向上连续 1 的高度压出来,再把每一行的高度从大到小排队,站在第 j 根柱子上就有一个 高乘 j 的候选矩形,全程取最大。下面先从压高度开始。
阶段一 · 按列压出向上连续 1 的高度 h：这就是 3 行 3 列的原矩阵,蓝色是 0,绿色是 1。第一步,把每个格子换算成它「向上连续 1 的高度」,记成 h。规则很简单,格子本身是 0 就记 0;本身是 1,就看它正上方那个格子的 h 是几,再加 1。咱们从第 0 行开始,一行一行、从左到右地压。
压高度 · 格子 (0,0) → 0：看格子 (0,0),它本身是 0,向上根本接不上 1,高度直接记 0。
压高度 · 格子 (0,1) → 0：看格子 (0,1),它本身是 0,向上根本接不上 1,高度直接记 0。
压高度 · 格子 (0,2) → 1：看格子 (0,2),它是 1,又在最顶上一行,上面没有别人了,向上连续的 1 只有它自己,高度记 1。
压高度 · 格子 (1,0) → 1：看格子 (1,0),它是 1。看它正上方那个格子的高度是 0,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 0 加 1,等于 1。
压高度 · 格子 (1,1) → 1：看格子 (1,1),它是 1。看它正上方那个格子的高度是 0,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 0 加 1,等于 1。
压高度 · 格子 (1,2) → 2：看格子 (1,2),它是 1。看它正上方那个格子的高度是 1,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 1 加 1,等于 2。
压高度 · 格子 (2,0) → 2：看格子 (2,0),它是 1。看它正上方那个格子的高度是 1,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 1 加 1,等于 2。
压高度 · 格子 (2,1) → 0：看格子 (2,1),它本身是 0,向上根本接不上 1,高度直接记 0。
压高度 · 格子 (2,2) → 3：看格子 (2,2),它是 1。看它正上方那个格子的高度是 2,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 2 加 1,等于 3。
阶段一完成 · 高度表 h 全压好：九个格子的高度都压好了。第 0 行是 0、0、1,第 1 行是 1、1、2,第 2 行是 2、0、3。这里的 3 就表示这个格子向上能连着三个 1。原来的二维矩阵,现在变成了三行「柱子高度」。接下来的重排和数矩形,全在每一行内部做。
阶段二 · 每一行:高度从大到小排,再扫最大矩形：第二步数矩形。因为列可以随意换位置,把某一行的这排高度想成一排能自由挪动的柱子。要在里面找一块全 1 的大矩形,最聪明的排法就是从高到低排好、最高的靠最左。这样站在从左数第 j 根柱子上,它连同左边一共 j 根都不比它矮,正好托起一个 高等于它、宽等于 j 的矩形。咱们一行一行来,先看第 0 行。
第 0 行 · 原顺序的柱子：把第 0 行的三个高度 0、0、1 立成三根柱子,这是它们在原来列序下的样子。现在还乱着,先别急着数,下一帧把它们从高到低排队。
第 0 行 · 从大到小排好：把这排柱子从大到小排好队,变成 1、0、0,最高的挪到最左边。因为列本来就能随便换,这么排完全合法。排好之后有个好处:从左数任意第 j 根,它左边这一片全都不比它矮,能整整齐齐托起一个宽 j 的矩形。下面从最左那根开始,一根一根量矩形。
第 0 行 · 第 1 根 · 高1×宽1=1：站在从左数第 1 根柱子上,它高 1。它左边连它一共 1 根都不比它矮,于是能框出一个 高 1 乘 宽 1 的全 1 矩形,面积 1。这个 1 比之前的最大 0 还大,答案刷新成 1。
第 0 行 · 第 2 根 · 高0×宽2=0：走到从左数第 2 根,它的高度是 0,是根空柱子,托不起任何全 1 矩形,面积 0,不刷新答案。继续看第 3 根。
第 0 行 · 第 3 根 · 高0×宽3=0：走到从左数第 3 根,它的高度是 0,是根空柱子,托不起任何全 1 矩形,面积 0,不刷新答案。第 0 行到这里量完,本行最大是 1。
第 1 行 · 原顺序的柱子：把第 1 行的三个高度 1、1、2 立成三根柱子,这是它们在原来列序下的样子。现在还乱着,先别急着数,下一帧把它们从高到低排队。
第 1 行 · 从大到小排好：把这排柱子从大到小排好队,变成 2、1、1,最高的挪到最左边。因为列本来就能随便换,这么排完全合法。排好之后有个好处:从左数任意第 j 根,它左边这一片全都不比它矮,能整整齐齐托起一个宽 j 的矩形。下面从最左那根开始,一根一根量矩形。
第 1 行 · 第 1 根 · 高2×宽1=2：站在从左数第 1 根柱子上,它高 2。它左边连它一共 1 根都不比它矮,于是能框出一个 高 2 乘 宽 1 的全 1 矩形,面积 2。这个 2 比之前的最大 1 还大,答案刷新成 2。
第 1 行 · 第 2 根 · 高1×宽2=2：站在从左数第 2 根柱子上,它高 1。它左边连它一共 2 根都不比它矮,于是能框出一个 高 1 乘 宽 2 的全 1 矩形,面积 2。面积 2 没超过已有的最大 2,答案还是 2。
第 1 行 · 第 3 根 · 高1×宽3=3：站在从左数第 3 根柱子上,它高 1。它左边连它一共 3 根都不比它矮,于是能框出一个 高 1 乘 宽 3 的全 1 矩形,面积 3。这个 3 比之前的最大 2 还大,答案刷新成 3。
第 2 行 · 原顺序的柱子：把第 2 行的三个高度 2、0、3 立成三根柱子,这是它们在原来列序下的样子。现在还乱着,先别急着数,下一帧把它们从高到低排队。
第 2 行 · 从大到小排好：把这排柱子从大到小排好队,变成 3、2、0,最高的挪到最左边。因为列本来就能随便换,这么排完全合法。排好之后有个好处:从左数任意第 j 根,它左边这一片全都不比它矮,能整整齐齐托起一个宽 j 的矩形。下面从最左那根开始,一根一根量矩形。
第 2 行 · 第 1 根 · 高3×宽1=3：站在从左数第 1 根柱子上,它高 3。它左边连它一共 1 根都不比它矮,于是能框出一个 高 3 乘 宽 1 的全 1 矩形,面积 3。面积 3 没超过已有的最大 3,答案还是 3。
第 2 行 · 第 2 根 · 高2×宽2=4：站在从左数第 2 根柱子上,它高 2。它左边连它一共 2 根都不比它矮,于是能框出一个 高 2 乘 宽 2 的全 1 矩形,面积 4。这个 4 比之前的最大 3 还大,答案刷新成 4。
第 2 行 · 第 3 根 · 高0×宽3=0：走到从左数第 3 根,它的高度是 0,是根空柱子,托不起任何全 1 矩形,面积 0,不刷新答案。第 2 行到这里量完,本行最大是 4。
答案 · 最大全 1 子矩阵面积 = 4：三行都量完了。第 0 行最大 1,第 1 行最大 3,第 2 行最大 4,取最大就是 4。这块 4,正是第 2 行排序成 3、2、0 后,站在第 2 根柱子上量出的 高 2 乘 宽 2。它跟题面示例给的 4 完全吻合。整套路子就是:先按列压高度,再让每行从大到小排、扫 高乘位置序号 取最大。
边界想清:全 0 面积为 0;单行 1、0、1、0、1 排序后三根 1 相邻得 3;全 1 的 2 乘 2 底行两根高 2 挨一起得 4。
面试重点:重排等价于柱子任意摆、排序后第 j 根托起 高乘 j 的矩形、高度有界可用计数排序降到 O(m 乘 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 largestSubmatrix(self, matrix: List[List[int]]) -> int: for i in range(1, len(matrix)): for j in range(len(matrix[0])): if matrix[i][j]: matrix[i][j] = matrix[i - 1][j] + 1 ans = 0 for row in matrix: row.sort(reverse=True) for j, v in enumerate(row, 1): ans = max(ans, j * v) return ans复杂度
- 时间：O(m · n · log n)，m 是行数 n 是列数。压高度表把矩阵扫一遍是 O(m·n)。数矩形时,每一行要对 n 个高度排序,单行 O(n·log n),一共 m 行,合计 O(m·n·log n),排序是主导项
- 空间：不计排序 O(1);计排序 C++/Java O(log n)、Python O(n)，高度是原地压在输入 matrix 上,没另开高度表,辅助只用了答案等常数变量。排序内部开销:C++ 与 Java 递归栈约 O(log n),Python 的排序最坏 O(n)。按峰值,不计排序内部时是 O(1)
易错点
面试追问把动画讲成自己的话
追问为什么把每一行的高度从大到小排一下,就能算出这一行能贡献的最大矩形?
追问每行都排序,时间是 O(m 乘 n 乘 log n),还能更快吗?
追问为什么能原地把输入矩阵改成高度表,不额外开空间?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
获取食物的最短路径
LeetCode 1730 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题