重新排列后的最大子矩阵 图解题解
这道题到底在问什么
- 输入
- matrix=[[0,0,1],[1,1,1],[1,0,1]]
- 输出
- 4
- 输入
- matrix=[[1,0,1,0,1]]
- 输出
- 3
最优解：一步一步想明白
- 3记住这两步:先把每格向上连续 1 的高度压出来,再把每一行的高度从大到小排队,站在第 j 根柱子上就有一个 高乘 j 的候选矩形,全程取最大。下面先从压高度开始。
- 4蓝格 = 0,绿格 = 1,逐格换算成向上高度这就是 3 行 3 列的原矩阵,蓝色是 0,绿色是 1。第一步,把每个格子换算成它「向上连续 1 的高度」,记成 h。规则很简单,格子本身是 0 就记 0;本身是 1,就看它正上方那个格子的 h 是几,再加 1。咱们从第 0 行开始,一行一行、从左到右地压。
- 5本身是 0,h = 0看格子 (0,0),它本身是 0,向上根本接不上 1,高度直接记 0。
- 6本身是 0,h = 0看格子 (0,1),它本身是 0,向上根本接不上 1,高度直接记 0。
- 7h = 1看格子 (0,2),它是 1,又在最顶上一行,上面没有别人了,向上连续的 1 只有它自己,高度记 1。
- 8h = 1看格子 (1,0),它是 1。看它正上方那个格子的高度是 0,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 0 加 1,等于 1。
- 9h = 1看格子 (1,1),它是 1。看它正上方那个格子的高度是 0,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 0 加 1,等于 1。
- 10h = 2看格子 (1,2),它是 1。看它正上方那个格子的高度是 1,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 1 加 1,等于 2。
- 11h = 2看格子 (2,0),它是 1。看它正上方那个格子的高度是 1,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 1 加 1,等于 2。
- 12本身是 0,h = 0看格子 (2,1),它本身是 0,向上根本接不上 1,高度直接记 0。
- 13h = 3看格子 (2,2),它是 1。看它正上方那个格子的高度是 2,那从这里往上连续的 1 就是上面那一摞再加自己,高度记 2 加 1,等于 3。
- 14h = 每格向上连续 1 的高度九个格子的高度都压好了。第 0 行是 0、0、1,第 1 行是 1、1、2,第 2 行是 2、0、3。这里的 3 就表示这个格子向上能连着三个 1。原来的二维矩阵,现在变成了三行「柱子高度」。接下来的重排和数矩形,全在每一行内部做。
- 15把每行高度看成一排柱子,列可换位就是柱子可任意排第二步数矩形。因为列可以随意换位置,把某一行的这排高度想成一排能自由挪动的柱子。要在里面找一块全 1 的大矩形,最聪明的排法就是从高到低排好、最高的靠最左。这样站在从左数第 j 根柱子上,它连同左边一共 j 根都不比它矮,正好托起一个 高等于它、宽等于 j 的矩形。咱们一行一行来,先看第 0 行。
- 16高度(原列序):0、0、1把第 0 行的三个高度 0、0、1 立成三根柱子,这是它们在原来列序下的样子。现在还乱着,先别急着数,下一帧把它们从高到低排队。
- 17排序后:1、0、0(最高靠左)把这排柱子从大到小排好队,变成 1、0、0,最高的挪到最左边。因为列本来就能随便换,这么排完全合法。排好之后有个好处:从左数任意第 j 根,它左边这一片全都不比它矮,能整整齐齐托起一个宽 j 的矩形。下面从最左那根开始,一根一根量矩形。
- 18候选面积 = 1 × 1 = 1站在从左数第 1 根柱子上,它高 1。它左边连它一共 1 根都不比它矮,于是能框出一个 高 1 乘 宽 1 的全 1 矩形,面积 1。这个 1 比之前的最大 0 还大,答案刷新成 1。
- 19空柱子,面积 0走到从左数第 2 根,它的高度是 0,是根空柱子,托不起任何全 1 矩形,面积 0,不刷新答案。继续看第 3 根。
- 20空柱子,面积 0走到从左数第 3 根,它的高度是 0,是根空柱子,托不起任何全 1 矩形,面积 0,不刷新答案。第 0 行到这里量完,本行最大是 1。
- 21高度(原列序):1、1、2把第 1 行的三个高度 1、1、2 立成三根柱子,这是它们在原来列序下的样子。现在还乱着,先别急着数,下一帧把它们从高到低排队。
- 22排序后:2、1、1(最高靠左)把这排柱子从大到小排好队,变成 2、1、1,最高的挪到最左边。因为列本来就能随便换,这么排完全合法。排好之后有个好处:从左数任意第 j 根,它左边这一片全都不比它矮,能整整齐齐托起一个宽 j 的矩形。下面从最左那根开始,一根一根量矩形。
- 23候选面积 = 2 × 1 = 2站在从左数第 1 根柱子上,它高 2。它左边连它一共 1 根都不比它矮,于是能框出一个 高 2 乘 宽 1 的全 1 矩形,面积 2。这个 2 比之前的最大 1 还大,答案刷新成 2。
- 24候选面积 = 1 × 2 = 2站在从左数第 2 根柱子上,它高 1。它左边连它一共 2 根都不比它矮,于是能框出一个 高 1 乘 宽 2 的全 1 矩形,面积 2。面积 2 没超过已有的最大 2,答案还是 2。
- 25候选面积 = 1 × 3 = 3站在从左数第 3 根柱子上,它高 1。它左边连它一共 3 根都不比它矮,于是能框出一个 高 1 乘 宽 3 的全 1 矩形,面积 3。这个 3 比之前的最大 2 还大,答案刷新成 3。
- 26高度(原列序):2、0、3把第 2 行的三个高度 2、0、3 立成三根柱子,这是它们在原来列序下的样子。现在还乱着,先别急着数,下一帧把它们从高到低排队。
- 27排序后:3、2、0(最高靠左)把这排柱子从大到小排好队,变成 3、2、0,最高的挪到最左边。因为列本来就能随便换,这么排完全合法。排好之后有个好处:从左数任意第 j 根,它左边这一片全都不比它矮,能整整齐齐托起一个宽 j 的矩形。下面从最左那根开始,一根一根量矩形。
- 28候选面积 = 3 × 1 = 3站在从左数第 1 根柱子上,它高 3。它左边连它一共 1 根都不比它矮,于是能框出一个 高 3 乘 宽 1 的全 1 矩形,面积 3。面积 3 没超过已有的最大 3,答案还是 3。
- 29候选面积 = 2 × 2 = 4站在从左数第 2 根柱子上,它高 2。它左边连它一共 2 根都不比它矮,于是能框出一个 高 2 乘 宽 2 的全 1 矩形,面积 4。这个 4 比之前的最大 3 还大,答案刷新成 4。
- 30空柱子,面积 0走到从左数第 3 根,它的高度是 0,是根空柱子,托不起任何全 1 矩形,面积 0,不刷新答案。第 2 行到这里量完,本行最大是 4。
- 31所有行、所有位置里最大的候选面积 = 4三行都量完了。第 0 行最大 1,第 1 行最大 3,第 2 行最大 4,取最大就是 4。这块 4,正是第 2 行排序成 3、2、0 后,站在第 2 根柱子上量出的 高 2 乘 宽 2。它跟题面示例给的 4 完全吻合。整套路子就是:先按列压高度,再让每行从大到小排、扫 高乘位置序号 取最大。
⚠️ 容易写错的地方
✗ 错：把「列可重排」理解成整块矩阵能任意打乱
✓ 对：只能整列搬动,一列里的上下关系不变
正因为列内不变,才能先按列压出向上高度,再靠排列凑相邻
✗ 错：压高度时忘了本身是 0 要清零
✓ 对：本身是 0 高度记 0,是 1 才接正上方加 1
一旦中间有 0,向上的连续 1 就被截断,高度必须从这里断开
✗ 错：每行不排序,直接按原列序数矩形
✓ 对：先把该行高度从大到小排,再扫
列能随便换,排成高到低才能让宽度里每根柱子都不比当前矮
✗ 错：矩形高度取成这一段的最大值
✓ 对：站在第 j 根柱子,矩形高就是这根柱子的高度
排序后第 j 根是这 j 根里最矮的,矩形要全 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 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 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 largestSubmatrix(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size();
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j]) {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
int ans = 0;
for (auto& row : matrix) {
sort(row.rbegin(), row.rend());
for (int j = 0; j < n; ++j) {
ans = max(ans, (j + 1) * row[j]);
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int largestSubmatrix(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
for (int i = 1; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == 1) {
matrix[i][j] = matrix[i - 1][j] + 1;
}
}
}
int ans = 0;
for (int[] row : matrix) {
Arrays.sort(row);
for (int j = n - 1, k = 1; j >= 0 && row[j] > 0; --j, ++k) {
int s = row[j] * k;
ans = Math.max(ans, s);
}
}
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 重新排列后的最大子矩阵 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么把每一行的高度从大到小排一下,就能算出这一行能贡献的最大矩形?+
因为题目允许整列任意重排,而压完高度后,每一列就是一根固定高度的柱子,重排列等价于把这排柱子任意摆放。要在一排柱子里找一块全 1 的矩形,矩形的高等于所选那几根里最矮的一根,宽等于根数。既然能随便摆,最优摆法一定是把要用的柱子按从高到低挨在一起。于是排好序后,站在从左数第 j 根柱子上,它连同左边一共 j 根都不比它矮,恰好托起一个 高等于它、宽等于 j 的矩形,逐根取最大就是这一行的最优。
每行都排序,时间是 O(m 乘 n 乘 log n),还能更快吗?+
能。注意压出的高度值都在 0 到 m 之间,是个有界的小范围整数,可以把比较排序换成计数排序,单行排序从 O(n log n) 降到 O(n)。这样整体就是 O(m 乘 n)。思路是每行开一个长度 m 加 1 的桶数一下各高度出现次数,再从高到低摊开扫。面试里能点出「高度有界、可用计数排序」是加分项。
为什么能原地把输入矩阵改成高度表,不额外开空间?+
压高度是自上而下、每个格子只依赖正上方那个已经算好的值,而下面的格子还没用到当前格的原始 0 或 1,所以就地把 matrix 改写成高度不会破坏后续计算。这样除了排序内部的少量开销,不需要再开一张同样大小的表,空间是常数级。如果面试要求不能改动入参,再另开一份拷贝即可,量级不变。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 重新排列后的最大子矩阵 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。