京公网安备11010502063487号给定一个只包含 0 和 1 的二维矩阵，找出只包含 1 的最大矩形，返回它的面积。这道题的巧妙之处是把它转化成上一题：把每一行当作矩形的底边，统计每一列"从这一行往上连续有多少个 1"，这就得到一个柱状图；这个柱状图里最大的矩形，就是以这一行为底边的最大全 1 矩形。对每一行都这样做一遍，取最大值。本文用真实数据比较这个做法与"枚举所有矩形"的耗时，给出五种语言的实现，并把逐行构造柱状图的过程做成分步演示。
完整题目见官方页面（链接在文末）。矩阵在测试里用字符串数组表示，每个字符串是一行。基准解用二维前缀和枚举所有矩形：一个矩形全是 1，当且仅当它里面所有格子的和等于它的面积，O(m²n²)，是与柱状图转化完全不同的写法。一共 13 组用例，覆盖：官方示例、单个格子（0 或 1）、单行、单列、全是 1、全是 0、中间有 0 的十字形：
输入 [["10100","10111","11111","10010"]] 输出 6 输入 [["0"]] 输出 0 输入 [["1"]] 输出 1 输入 [["00"]] 输出 0 输入 [["11"]] 输出 2 输入 [["1","1","1"]] 输出 3
heights[j] 表示当前行往上、第 j 列连续的 1 的个数：遇到 1 就加一，遇到 0 就清零。每处理完一行，heights 就是一个柱状图，调用上一题的单调栈函数求其中最大的矩形，更新全局最大值。因为矩形必须全是 1，所以柱子的高度必须是"连续的 1"，遇到 0 就断开，这正好由"清零"保证。Python、Java、Go、JavaScript、C++ 都是真实编译运行的；每种语言里的单调栈函数都与上一题的实现相同。
Python · 解法代码def largest_in_histogram(heights): # 与上一题（柱状图中最大的矩形）相同的单调栈 st = [] best = 0 n = len(heights) for i in range(n + 1): h = heights[i] if i < n else 0 while st and heights[st[-1]] >= h: height = heights[st.pop()] left = st[-1] if st else -1 best = max(best, height * (i - left - 1)) st.append(i) return best def solve(matrix_): n = len(matrix_[0]) heights = [0] * n # heights[j]：以当前行为底边，第 j 列向上连续的 1 有几个 best = 0 for row in matrix_: for j in range(n): heights[j] = heights[j] + 1 if row[j] == "1" else 0 best = max(best, largest_in_histogram(heights)) # 每一行的 heights 就是一个柱状图，求其中最大的矩形 return best
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [["10100","10111","11111","10010"]] → 6 [["0"]] → 0 [["1"]] → 1 [["00"]] → 0 [["11"]] → 2 [["1","1","1"]] → 3
Java · 解法代码class Solution { private int largest(int[] heights) { // 与上一题（柱状图中最大的矩形）相同的单调栈 Deque<Integer> st = new ArrayDeque<>(); int best = 0, n = heights.length; for (int i = 0; i <= n; i++) { int h = i < n ? heights[i] : 0; while (!st.isEmpty() && heights[st.peek()] >= h) { int height = heights[st.pop()]; int left = st.isEmpty() ? -1 : st.peek(); best = Math.max(best, height * (i - left - 1)); } st.push(i); } return best; } public int maximalRectangle(char[][] matrix) { int n = matrix[0].length; int[] heights = new int[n]; // heights[j]：以当前行为底边，第 j 列向上连续的 1 有几个 int best = 0; for (char[] row : matrix) { for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0; best = Math.max(best, largest(heights)); // 每一行的 heights 就是一个柱状图，求其中最大的矩形 } return best; } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [["10100","10111","11111","10010"]] → 6 [["0"]] → 0 [["1"]] → 1 [["00"]] → 0 [["11"]] → 2 [["1","1","1"]] → 3
Go · 解法代码func largest(heights []int) int { // 与上一题（柱状图中最大的矩形）相同的单调栈 st := []int{} best, n := 0, len(heights) for i := 0; i <= n; i++ { h := 0 if i < n { h = heights[i] } for len(st) > 0 && heights[st[len(st)-1]] >= h { height := heights[st[len(st)-1]] st = st[:len(st)-1] left := -1 if len(st) > 0 { left = st[len(st)-1] } if area := height * (i - left - 1); area > best { best = area } } st = append(st, i) } return best } func maximalRectangle(matrix [][]byte) int { n := len(matrix[0]) heights := make([]int, n) // heights[j]：以当前行为底边，第 j 列向上连续的 1 有几个 best := 0 for _, row := range matrix { for j := 0; j < n; j++ { if row[j] == '1' { heights[j]++ } else { heights[j] = 0 } } if a := largest(heights); a > best { // 每一行的 heights 就是一个柱状图，求其中最大的矩形 best = a } } return best }
$ go build -o bin . && ./bin < cases.jsonl [["10100","10111","11111","10010"]] → 6 [["0"]] → 0 [["1"]] → 1 [["00"]] → 0 [["11"]] → 2 [["1","1","1"]] → 3
JavaScript · 解法代码function largest(heights) { // 与上一题（柱状图中最大的矩形）相同的单调栈 const st = []; let best = 0; const n = heights.length; for (let i = 0; i <= n; i++) { const h = i < n ? heights[i] : 0; while (st.length > 0 && heights[st[st.length - 1]] >= h) { const height = heights[st.pop()]; const left = st.length > 0 ? st[st.length - 1] : -1; best = Math.max(best, height * (i - left - 1)); } st.push(i); } return best; } function maximalRectangle(matrix) { // matrix 是字符串数组，每个字符串是一行 const n = matrix[0].length; const heights = new Array(n).fill(0); // heights[j]：以当前行为底边，第 j 列向上连续的 1 有几个 let best = 0; for (const row of matrix) { for (let j = 0; j < n; j++) heights[j] = row[j] === "1" ? heights[j] + 1 : 0; best = Math.max(best, largest(heights)); // 每一行的 heights 就是一个柱状图，求其中最大的矩形 } return best; }
$ node run.js < cases.jsonl [["10100","10111","11111","10010"]] → 6 [["0"]] → 0 [["1"]] → 1 [["00"]] → 0 [["11"]] → 2 [["1","1","1"]] → 3
C++ · 解法代码#include <algorithm> #include <vector> using namespace std; class Solution { int largest(vector<int>& heights) { // 与上一题（柱状图中最大的矩形）相同的单调栈 vector<int> st; int best = 0, n = heights.size(); for (int i = 0; i <= n; i++) { int h = i < n ? heights[i] : 0; while (!st.empty() && heights[st.back()] >= h) { int height = heights[st.back()]; st.pop_back(); int left = st.empty() ? -1 : st.back(); best = max(best, height * (i - left - 1)); } st.push_back(i); } return best; } public: int maximalRectangle(vector<vector<char>>& matrix) { int n = matrix[0].size(); vector<int> heights(n, 0); // heights[j]：以当前行为底边，第 j 列向上连续的 1 有几个 int best = 0; for (auto& row : matrix) { for (int j = 0; j < n; j++) heights[j] = row[j] == '1' ? heights[j] + 1 : 0; best = max(best, largest(heights)); // 每一行的 heights 就是一个柱状图，求其中最大的矩形 } return best; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [["10100","10111","11111","10010"]] → 6 [["0"]] → 0 [["1"]] → 1 [["00"]] → 0 [["11"]] → 2 [["1","1","1"]] → 3
共 13 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 13/13 Java 通过 13/13 Go 通过 13/13 JavaScript 通过 13/13 C++ 通过 13/13
矩阵边长 m = n 分别为 10、20、40、300，格子里 1 和 0 按一个规律的图案排列，每个规模取三次中最快的一次：
m = n | 暴力解 | 本文解法
10 | 0.221 ms | 0.020 ms
20 | 3.753 ms | 0.072 ms
40 | 53.933 ms | 0.260 ms
300 | （未测，太慢） | 13.856 ms枚举所有矩形的耗时随边长每翻一倍增长约 14 到 17 倍（0.221ms、3.753ms、53.933ms），符合 O(m²n²) 即边长的四次方（翻倍是 16 倍）；本文解法每翻一倍增长约 3.6 倍（0.020ms、0.072ms、0.260ms），符合 O(mn) 即边长的平方（翻倍是 4 倍）。40×40 时枚举 53.9ms，本文解法 0.26ms，约 207 倍。300×300 时本文解法用了 13.9ms，枚举在这个规模没有测。
另外我单独复测了一次这三个规模，并且确认两种做法的最大面积一致：
m×n 的矩阵：单调栈（每行一次柱状图，O(mn)）vs 全部矩形枚举 + 前缀和（O(m²n²)），各取三次中最快 10×10: 单调栈 0.019 ms 枚举所有矩形 0.21 ms 最大面积一致：True（10） 20×20: 单调栈 0.069 ms 枚举所有矩形 3.05 ms 最大面积一致：True（20） 40×40: 单调栈 0.263 ms 枚举所有矩形 54.00 ms 最大面积一致：True（40）
Python 版本另外和枚举所有矩形做了随机对拍：行数、列数各取 1 到 6，每个格子是 1 的概率取 40%、70% 或 90%：
随机对拍 10000 组（行数、列数各取 1 到 6，每个格子是 1 的概率取 40%、70% 或 90%），solve 与 brute 的结果全部一致。
另外四种语言只在上面 13 组固定用例上验证过，没有做大规模随机对拍。
下面的演示用官方示例 ["10100", "10111", "11111", "10010"]，答案是 6。第 0 行 heights = [1, 0, 1, 0, 0]，最大矩形面积 1；第 1 行 [2, 0, 2, 1, 1]，最大矩形面积 3（右边三列高度 2、1、1，取高 1 宽 3）；第 2 行 [3, 1, 3, 2, 2]，面积 6（右边三列 3、2、2 … 高度取 2，宽度 3）；第 3 行 [4, 0, 0, 3, 0]，面积 4。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示的最终结果与 solve 的返回值一致。