题目描述
思路解析
一句话答案：LeetCode 1727 重新排列后的最大子矩阵：列可整列重排，先把每列连续的 1 压成高度、每行从大到小排，站第 j 根柱子就有 j 乘高的矩形，逐根取最大，时间 O(m·n·log n)。
整列搬动之后，全 1 矩形最大能有多大
给一个 m 行 n 列、只装 0 和 1 的矩阵 matrix，你能把任意几列整列换位置，但一列里的上下格子必须原样跟着走。问重排之后全是 1 的矩形面积最大是多少。题面 matrix=[[0,0,1],[1,1,1],[1,0,1]] 把带 1 的列凑一起能框出 2 乘 2 全 1 块，面积 4；单行 matrix=[[1,0,1,0,1]] 把三个 1 挪到相邻，是一条长 3 的横条。
列能排出 n 的阶乘种顺序，挨个试排不动
n 列能排出 n 的阶乘那么多种顺序，枚举每种排法找矩形根本跑不完。但重排只挪列的左右位置，从没打乱过一列内部的上下关系——正因为列内锁死，一个格子向上连着几个 1，是重排前后都不变的量。抓住这个不变量，二维搬列就能拆成一行行分开算。
压高度：把每列连续的 1 累成一个数
第一步压高度，也就是把每列向上连续的 1 累成一个高度值：格子是 0 就记 0，是 1 就等于正上方那格的高度再加 1。压完，每列成了一根固定高度的柱子，重排列就是把这排柱子随意挪位置。
第二步在每行里数矩形。柱子能随便摆，最省的摆法就是把用到的柱子从高到低挨在一起。把这行高度从大到小排好，站在从左数第 j 根柱子上，它连同左边一共 j 根都不比它矮，恰好托起高等于它、宽等于 j 的矩形，面积就是 j 乘这根的高度，逐根取最大即可。
矩形的高，为什么取当前这根而不是最高那根
排完序，第 j 根柱子是左边这 j 根里最矮的一根。矩形要全是 1，高就被最矮那根卡死，矩形高只能取它自己、宽取 j。若图省事拿这片里的最高值当高，上半截会戳进矮柱子的 0 空当，矩形就不再全是 1。
拿题面 3 乘 3 矩阵逐格演一遍
先压高度。第 0 行在最顶上、没得接，原样 0、0、1。第 1 行都是 1，正上方高度 0、0、1 各加 1 得 1、1、2。第 2 行原始 1、0、1：头一个正上方 1 加 1 得 2，中间 0 记 0，末一个正上方 2 加 1 得 3，压成 2、0、3。
再一行行排序数矩形。第 0 行排成 1、0、0，第 1 根 1 乘 1 得 1，后两根空柱记 0。第 1 行排成 2、1、1，第 1 根 2 乘 1 得 2，第 2 根 1 乘 2 得 2，第 3 根 1 乘 3 得 3。第 2 行排成 3、2、0，第 1 根 3 乘 1 得 3，第 2 根 2 乘 2 得 4，第 3 根归零。三行各自最大是 1、3、4，取最大答案 4。
忘了清零、省掉排序，矩形就立不住
压高度扫一遍矩阵是 O(m 乘 n)；数矩形每行给 n 个高度排序，单行 O(n 乘 log n)，m 行合计 O(m 乘 n 乘 log n)，排序是主导项。高度原地压在输入 matrix 上、没另开表，辅助只有常数变量，不计排序内部空间 O(1)。
两处一错就前功尽弃：压高度时忘了本身 0 的格子清零，高度虚高，量出的矩形混进 0；每行省掉排序、按原列序扫，宽度里可能夹根矮柱子，全 1 矩形立不住。边界也想清：全 0 矩阵面积 0；单行 1、0、1、0、1 排序后三根 1 相邻，得长 3 的横条。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这两步:先把每格向上连续 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题