黑白纸片题解：从二维矩阵到单调栈，最大全黑矩形面积详解

1. 题目原题：黑白纸片到底求什么

1.1 回忆版题目描述

3月15号上午顺丰春招笔试，第二题叫《黑白纸片》，刷了一圈讨论区，考生普遍反馈：题面很好懂，真正写起来才发现建模才是关键。我先把回忆版的题面整理如下（细节上可能有出入，但数据范围、样例基本一致）：

小顺用黑白纸片拼了一张 n 行 m 列的装饰画，每个格子里有一片纸片，黑色用1表示，白色用0表示。小顺想从画布中裁下一块矩形区域，要求这块区域里所有纸片都必须是黑色，想请你求出这个矩形区域的最大面积。

输入第一行是两个整数 n, m，范围是 1 ≤ n, m ≤ 500。接下来 n 行，每行是一个长度为 m 的01字符串，代表当前行的纸片颜色。输出一个整数，表示最大全黑矩形面积；如果整个画布没有黑色纸片，输出 0。

从题型上看，这个问题本质上是“最大全黑矩形”问题，英文社区里叫 Maximal Rectangle。它并不要求黑色区域是四连通或者八连通的块，只需要在几何上是一个矩形，内部没有白色就行。这一点很容易和“最大连通块”搞混，我考场上第一眼也差点想去写 BFS。

1.2 样例推演：为什么答案不是8而是6

题目给了这样一组样例：

输入：

4 5 10100 10111 11111 10010

输出：

6

我第一次看到这个样例，默认答案是 8，因为第一列四行都是1，看起来可以切一个 4×1 的矩形，面积 4；第二行到第三行最右侧三列也是1，面积 2×3=6；那为什么不是更大呢？仔细看矩阵：

• 第 1 行：10100，只有第 1、3 列是黑色；
• 第 2 行：10111，第 1、3、4、5 列是黑色；
• 第 3 行：11111，五列全黑；
• 第 4 行：10010，第 1、4 列是黑色。

能形成一个完整全黑矩形的最大区域，是从第 2 行到第 3 行、第 3 列到第 5 列，形状是 2×3，面积 6。再往下扩一行，第 4 行的第 3、5 列是白色，矩形就破了；往左扩到第 1 列，第 2 行的第 2 列是白色，矩形也破了。所以答案不是拍脑袋能看出来的，尤其是数据规模到 500 之后，必须找规律。

这个样例还有另一个作用：提醒你输入是字符串，不是用空格分隔的数字。很多人在 Java 里用nextInt()读完 n 和 m 之后，直接用nextInt()读矩阵，结果读到一堆空指针或者解析错误，就是因为01矩阵是字符串。

1.3 看到这题先想清楚的两件事

第一，矩形是“满黑矩形”，不是“黑纸片连通块”。如果是连通块，我们可以 DFS/BFS 标记；但矩形要求内部不能有白色，要同时满足行方向连续和列方向连续，是一个更苛刻的几何约束。

第二，题目问的是最大面积，不是最大边长，也不是区域坐标。输出一个整数，说明我们只需要在计算过程中维护一个最大值，不需要回溯路径。这样数据结构上的选择就自由很多。

读题倒不难，难的是在 500×500 的数据范围内把复杂度压到可以接受。如果一开始就想到暴力枚举四个边界，多半会在测试用例上超时。

2. 从暴力枚举到“按行扫描”：二维压缩成一维的关键一步

2.1 暴力解法的时间账

先算一笔账：枚举矩形的左上角需要 nm 种选择，右下角也需要 nm 种选择，检查矩形是否全黑还要 O(nm)，总复杂度是 O(n^3m^3) 级别，完全不可行。就算提前做二维前缀和，把“检查是否全黑”优化成 O(1)，整体复杂度依然是 O(n^2*m^2)，也就是枚举四个边界。n=m=500 时，500^4 = 625 亿，内存和时间都过不去。

即使换一种枚举方式：枚举上下边界 O(n^2)，然后对每一列用前缀和维护该列在两边界之间的累加值，再扫描列求“连续满足条件的最长长度”，复杂度可以降到 O(n^2m)。500^3 = 1.25 亿，C++ 勉强能跑，Java 和 Python 压力很大。所以这道题真正合适的解法是 O(nm) 的单调栈。

很多同学觉得“能优化到 1.25 亿已经不错了”，但笔试系统不会给你宽松的常数时间，尤其 Java、Python 在这种复杂度下很容易吃 TLE。既然存在更优解法，就应该直接往正确方向想。

2.2 高度数组：把每一列连续黑纸片的数量记下来

单调栈解法的第一步是定义高度。我们用heights[j]表示当前扫描到第 i 行时，第 j 列从上到下连续黑色纸片的数量。

具体维护规则：

• 当当前位置是1时，heights[j]++，表示这一列可以继续往上“叠”黑纸片；
• 当当前位置是0时，heights[j] = 0，表示这一列的白纸片打断了连续黑色段，高度清零。

每处理完一行，我们都把当前的heights数组看成一个直方图。比如样例处理到第 3 行时，各列高度分别是3, 1, 3, 2, 2。直方图上的最大矩形面积是多少？看第 3 列到第 5 列，最小高度是 2，宽度是 3，面积就是 6。这正好和样例答案对应上了。

为什么只看每一列的高度就够？因为任何一个全黑矩形，我们在它的“底边”所在行看：矩形覆盖的那些列，每一列从底边往上至少都有矩形高度那么多个连续的1。也就是说，这些列的heights值都 ≥ 矩形高度。直方图求最大矩形，正好就是找一个高度，让它能向左向右延伸出尽量宽的区间，和矩形在原矩阵中的位置一一对应。

2.3 为什么扫描每一行就能覆盖所有全黑矩形

想证明不漏其实很简单：任取一个全黑矩形 R，它的底边一定在矩阵中的某一行 bottomRow，高度为 h，宽度为 w。因为 R 内部全部是黑色，所以对 R 覆盖的每一列，从 bottomRow 往上数，至少要连续 h 个黑色格子。于是当程序扫描到 bottomRow 这一行时，heights里这些列的值都至少是 h。此时对这个直方图调用“求最大矩形面积”，得到的答案一定 ≥ h*w。由于 R 是任意的，全局最大值一定能被覆盖。

可以再换一个角度理解：矩形一定有一个下边界，下边界所在行就是“底边所在行”。这一行扫描时的高度，不是指当前格子的颜色，而是指这一列从当前行向上连续黑格数量。如果列上有白色，高度就会在白色那一行清零，所以高度数组天然记录了一个矩形能向上的“天花板”。

到这里，核心转变就完成了：二维矩阵最大全黑矩形 = 对每一行生成的直方图求最大矩形面积，再对所有行取最大值。问题从二维降到了一维。

3. 柱状图最大矩形：单调栈的推演与边界细节

3.1 直方图模型

现在我们有若干个高度不等的柱子，比如heights = [2, 1, 5, 6, 2, 3]。要求在这个直方图里找一个面积最大的矩形：矩形底边必须与柱子的底对齐，高度不能超过覆盖区域内的最矮柱。

一个非常直观但容易错的想法：对每一根柱子，以它的高度为矩形高度，然后向左右扩展，直到遇到比它矮的柱子停下。这样得到的宽度就是它能影响的区间。这个思路的关键在于，任何一个最大矩形，其高度一定等于矩形区域内某根柱子的高度。因为如果矩形高度低于区域内所有柱子的高度，矩形还可以继续向上抬高，面积变大。所以枚举每根柱子作为“最低高度”，就是完备的。

3.2 单调栈到底存什么

单调栈保存的是柱子的下标，并且从栈底到栈顶的下标对应的柱子高度是递增的（准确说是非递减）。为什么要存下标而不是高度？因为计算宽度时下标差才是关键，高度可以通过下标去数组里取。

算法从左往右遍历每个柱子：

• 如果当前柱子高度大于等于栈顶柱子高度，直接入栈，因为当前柱子不会限制栈顶柱子的向右延伸，此时栈顶柱子能往右扩展的右边界还不确定。
• 如果当前柱子高度小于栈顶柱子高度，说明栈顶柱子向右已经碰到了一个“更矮的墙”，它无法再延伸了。于是弹出栈顶柱子，记为 h，以 h 为矩形高度，矩形的右边界就是当前的 i，左边界就是弹出后新栈顶指向的下标。宽度是i - left - 1，面积是h * width。

手动推演一下[2, 1, 5, 6, 2, 3]，在数组后面添加一个高度 0 的哨兵。遍历过程大致是：

• i=0，h=2，栈空，入栈下标 0。
• i=1，h=1，栈顶高度 2 > 1，弹出下标 0，h=2，栈空 left=-1，width = 1 - (-1) - 1 = 1，面积 2；然后入栈下标 1。
• i=2，h=5，5 > 1，入栈 [1,2]。
• i=3，h=6，6 > 5，入栈 [1,2,3]。
• i=4，h=2，6 > 2 弹出下标 3，h=6，此时栈顶是下标 2，left=2，width = 4 - 2 - 1 = 1，面积 6；接着 5 > 2 弹出下标 2，h=5，栈顶是下标 1，left=1，width = 4 - 1 - 1 = 2，面积 10。最大面积就在这里面产生。

这个推演能帮助你理解，为什么弹出时计算面积是对的：因为当前这个矮柱子，就是右侧第一个让栈顶柱子无法延伸的边界。

3.3 哨兵位的使用与弹出时宽度计算

上述推演里出现了 left=-1 的情况。很多初学者会在这里写错：弹出后直接width = i - stack.pop() - 1，或者不处理栈空，导致宽度少算。栈空意味着弹出柱子的左边没有更矮的柱子，它其实是当前区间内的最矮柱，左边界应该取到数组最左侧，也就是 -1 这个虚拟位置。

处理栈空有两条路：

• 要么在代码里判断stack.isEmpty() ? -1 : stack.peek()；
• 要么在数组的 0 号位置预先放一个高度为 0 的哨兵，这样栈永远不为空，但需要把真实列下标往后挪一位。Java 代码里就可以采用两侧哨兵的做法，代码会简洁很多。

还有一个细节：while 条件是heights[stack.peek()] > heights[i]，不是>=。遇到高度相等时不弹出，而是让新柱子入栈。这样做的原因是相等高度不应该作为“更矮的墙”。如果你使用>=也能通过，但会导致相等高度过早出栈，面积计算时宽度边界会变，容易出错；用>语义更直接：只有严格变矮时，才确定右边界。

时间复杂度上，每个下标最多入栈一次、出栈一次，因此一次直方图计算是 O(m)。总共有 n 行，所以整体 O(n*m)，空间复杂度 O(m)。这个复杂度对 500×500 的数据来说非常宽裕。

4. Java、C++、Python 三种实现逐段精讲

4.1 Java 版本：带哨兵的高度数组

Java 代码：

import java.util.ArrayDeque; import java.util.Deque; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); sc.nextLine(); int[] heights = new int[m + 2]; int ans = 0; for (int i = 0; i < n; i++) { String row = sc.nextLine(); for (int j = 0; j < m; j++) { if (row.charAt(j) == '1') { heights[j + 1]++; } else { heights[j + 1] = 0; } } ans = Math.max(ans, largestRectangleInHistogram(heights)); } System.out.println(ans); sc.close(); } private static int largestRectangleInHistogram(int[] heights) { Deque<Integer> stack = new ArrayDeque<>(); int maxArea = 0; for (int i = 0; i < heights.length; i++) { while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) { int h = heights[stack.pop()]; int left = stack.peek(); int width = i - left - 1; maxArea = Math.max(maxArea, h * width); } stack.push(i); } return maxArea; } }

这段代码有几个刻意设计：

• heights的长度是m + 2，下标0和m + 1永远是 0。更新时只更新j + 1到真实位置。
• 这样在largestRectangleInHistogram中弹出柱子后，stack.peek()一定不会为空，因为高度 0 的左侧哨兵永远在栈底。最后一个下标m + 1的高度 0 作为右侧哨兵，会把栈里所有高度大于 0 的柱子全部弹出。
• Java 的Deque推荐用ArrayDeque，比LinkedList快一些；这里用它作为栈来用，push、pop、peek都很自然。

4.2 C++ 版本：vector + stack 的标准写法

C++ 代码：

#include <bits/stdc++.h> using namespace std; int largestRectangleArea(vector<int>& heights) { stack<int> st; int maxArea = 0; for (int i = 0; i < heights.size(); ++i) { while (!st.empty() && heights[st.top()] > heights[i]) { int h = heights[st.top()]; st.pop(); int left = st.empty() ? -1 : st.top(); int width = i - left - 1; maxArea = max(maxArea, h * width); } st.push(i); } return maxArea; } int main() { int n, m; cin >> n >> m; vector<int> heights(m + 1, 0); int ans = 0; for (int i = 0; i < n; ++i) { string row; cin >> row; for (int j = 0; j < m; ++j) { if (row[j] == '1') { heights[j]++; } else { heights[j] = 0; } } ans = max(ans, largestRectangleArea(heights)); } cout << ans << endl; return 0; }

说明几点：

• heights开m + 1，最后一个元素永远是 0，它就是右侧哨兵；更新真实记录时使用j，不会污染最后一个位置。
• 因为左侧没有哨兵，弹出后需要判断st.empty()，为空时left = -1。
• bits/stdc++.h是竞赛常用头文件，如果你在工程项目里用，也可以换成<iostream>、<vector>、<stack>、<string>、<algorithm>，不影响逻辑。

4.3 Python 版本：列表模拟栈，简洁但不失性能

Python 代码：

def largest_rectangle(heights): heights = heights + [0] stack = [] max_area = 0 for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: height = heights[stack.pop()] left = stack[-1] if stack else -1 width = i - left - 1 max_area = max(max_area, height * width) stack.append(i) return max_area def main(): n, m = map(int, input().split()) heights = [0] * m ans = 0 for _ in range(n): row = input().strip() for j, ch in enumerate(row): if ch == '1': heights[j] += 1 else: heights[j] = 0 ans = max(ans, largest_rectangle(heights)) print(ans) if __name__ == "__main__": main()

Python 版本要注意：

• heights = heights + [0]会创建一个新列表，不会污染原来的heights，这个细节很重要。如果直接heights.append(0)，下一次调用largest_rectangle时列表长度会多 1，数据更新只更新前 m 个位置，导致多余的 0 一直堆积。
• stack里存的是下标。用stack[-1]模拟 peek。
• 在复杂度上，Python 的列表操作和while循环足够应对 500×500；如果是 2000×2000 的输入，建议改用 PyPy 跑。

4.4 三个版本放在一起的差异对比

三个版本的核心逻辑完全一致：每一行做完高度累加后，调用一次直方图最大值函数。所以只要单个函数是对的，整体就是对的。我建议大家在本地把这三个版本都跑一遍，目的不是背诵代码，而是体会同一套算法在不同语言里的表达差异。

5. 在线测试与自测用例：怎么确认你的代码真的能过

5.1 用题目样例做冒烟测试

样例输入前面已经给过。本地运行方式分别是：

• Java：javac Main.java && java Main
• C++：g++ -std=c++17 main.cpp -o main && ./main
• Python：python3 main.py

输入完矩阵后，三份代码都应该输出6。

如果你在牛客、力扣或者其他支持在线代码运行的页面做测试，注意把输入格式改成平台要求的输入方式；如果平台已经给你函数接口，只需要把largestRectangleArea的逻辑封装进去就行，输入输出部分可以去掉。

5.2 针对边界条件的额外用例

我考后整理了几个边界测试，很容易暴露问题：

“一字型”和“全黑”主要是验证哨兵是否正常工作；“有空洞矩阵”验证是否会把有空洞的区域当整块矩形；“全白”验证最终结果会不会被错误地初始化为非 0 值。

5.3 常见翻车点：行字符串读取、高度清零、宽度计算

先说读取：Java 里nextInt()不会吃掉行尾换行，所以读完 n、m 之后必须执行一次sc.nextLine()，否则第一次nextLine()会读到一个空串。C++ 的cin >> row会自动跳过空白，所以没有这个烦恼。Python 的input().strip()会把首尾空白去掉，也安全。

再说高度清零：很多人在遇到0时忘记把高度置为 0，导致这一列的黑色段被跨过白色纸片“续命”。这是整个算法最容易错的地方。一处白色就会让矩形破裂，所以清零不是可选项。

最后是宽度计算：width = i - left - 1里的i是当前遍历到的下标，不是已经弹出的那个下标。如果你把i写成弹出的下标，面积会变成h * 1，一定错。C++ 和 Python 在弹出后栈空时必须给left = -1，否则第一根柱子永远算不出正确宽度。

6. 变体与考场心得：下一个“黑白纸片”你还怕吗

6.1 变体一：改成最大全黑正方形

如果题目把矩形改成正方形，就换一道经典 DP。定义dp[i][j]表示以(i,j)为右下角能构成的最大全黑正方形边长，状态转移为：

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1（当matrix[i][j] == '1'时）

答案取所有dp[i][j]的最大值平方。这个 DP 的直觉是：一个更大的正方形，必然由其左上角、正上方、正左方三个较小的正方形同时支撑。

如果顺丰春招下一套题把“矩形”限制成“正方形”，你只需要在直方图解法上做一点变化，或者直接用 DP。很多人在考场上遇到“最大矩形”后，下一道“最大正方形”反而发懵，就是因为没有意识到这两种题型可以互相转化。

6.2 变体二：可以翻转一个区间该怎么做

假设题目变成“可以把一个子矩形内所有纸片翻转（黑变白、白变黑），然后求最大全黑矩形”，这就完全是另一个难度了。一般春招笔试第二题不会考到这种组合，但如果真出现，可以先从简化版入手：只翻转连续一行。再扩展到多行时，通常需要枚举翻转区域的上下边界，再用前缀和或者差分数组维护每个位置的翻转状态。这种题更适合写在第三题或者加试里。

我不建议在准备阶段死磕这种过于复杂的变体。先把单调栈和滑动窗口两类基础模型练熟，比什么都强。

6.3 我在这个题目上反复确认的三个点

第一，矩形和连通块一定要区分。考场上看到“黑色区域”四个字，第一反应很容易是 DFS 找连通块，但样例推演一下就会发现，DFS 会把两个被白色分开的黑色区域通过间接路径连起来，而矩形不允许这种情况。读题时花 30 秒把样例推算一遍，比写完整个 BFS 才发现方向错要好得多。

第二，二维矩阵题遇到“面积最值”，优先考虑一维化。最大全黑矩形、最大连续 1 的个数、接雨水这类问题，它们的共同解法都是“按行或者按列统计高度，再转成直方图”。一旦矩阵被压成一维数组，后面就可以交给单调栈或者滑动窗口，模型的复杂度瞬间降下来。

第三，样例过了不等于稳过。笔试时数据范围、字符格式、空数据这三个点最容易埋坑。习惯性在本地追加跑全 1、全 0、单行、单列四组测试。代码一旦在这些小输入上表现正常，至少不会因为低级错误丢分。

这道题本身不难，但它考察的核心能力是“把一个二维几何问题，用一行逻辑压缩成一维柱状图之后再用单调栈求解”。这种建模感，才是春招笔试真正想看到的。如果现在让我再进一次顺丰考场，看到“黑白纸片”我会觉得轻松不少，因为它背后就是一组非常成熟且可复现的套路。