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×36那为什么不是更大呢仔细看矩阵第 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)也就是枚举四个边界。nm500 时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 的哨兵。遍历过程大致是i0h2栈空入栈下标 0。i1h1栈顶高度 2 1弹出下标 0h2栈空 left-1width 1 - (-1) - 1 1面积 2然后入栈下标 1。i2h55 1入栈 [1,2]。i3h66 5入栈 [1,2,3]。i4h26 2 弹出下标 3h6此时栈顶是下标 2left2width 4 - 2 - 1 1面积 6接着 5 2 弹出下标 2h5栈顶是下标 1left1width 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) { DequeInteger 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(vectorint heights) { stackint 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; vectorint 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 三个版本放在一起的差异对比语言栈类型哨兵处理字符读取需要特别留意的地方JavaArrayDeque左右两侧哨兵nextLine读完 n,m 后手动 nextLine 吃掉换行Cstd::stack右侧哨兵 栈空 left-1cin row注意 vector 每次调用不追加哨兵Pythonlist 模拟栈每次复制列表追加右哨兵input().strip()不要在原 heights 上 append三个版本的核心逻辑完全一致每一行做完高度累加后调用一次直方图最大值函数。所以只要单个函数是对的整体就是对的。我建议大家在本地把这三个版本都跑一遍目的不是背诵代码而是体会同一套算法在不同语言里的表达差异。5. 在线测试与自测用例怎么确认你的代码真的能过5.1 用题目样例做冒烟测试样例输入前面已经给过。本地运行方式分别是Javajavac Main.java java MainCg -stdc17 main.cpp -o main ./mainPythonpython3 main.py输入完矩阵后三份代码都应该输出6。如果你在牛客、力扣或者其他支持在线代码运行的页面做测试注意把输入格式改成平台要求的输入方式如果平台已经给你函数接口只需要把largestRectangleArea的逻辑封装进去就行输入输出部分可以去掉。5.2 针对边界条件的额外用例我考后整理了几个边界测试很容易暴露问题用例输入期望输出单格白1 1 \n 00单格黑1 1 \n 11全黑 3x33 3 \n 111 \n 111 \n 1119一字型黑行1 5 \n 111115有空洞矩阵3 3 \n 101 \n 111 \n 1013全白 2x22 2 \n 00 \n 000“一字型”和“全黑”主要是验证哨兵是否正常工作“有空洞矩阵”验证是否会把有空洞的区域当整块矩形“全白”验证最终结果会不会被错误地初始化为非 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、单行、单列四组测试。代码一旦在这些小输入上表现正常至少不会因为低级错误丢分。这道题本身不难但它考察的核心能力是“把一个二维几何问题用一行逻辑压缩成一维柱状图之后再用单调栈求解”。这种建模感才是春招笔试真正想看到的。如果现在让我再进一次顺丰考场看到“黑白纸片”我会觉得轻松不少因为它背后就是一组非常成熟且可复现的套路。