• 文档
• 教程
• 知识库

导读

在计算机视觉、图像处理与算法竞赛中，常需要在 0/1 矩阵中寻找面积最大的全零矩形子矩阵。本文基于 cp-algorithms 仓库中的 zero_matrix.md 文档，完整讲解该经典问题的两种思路——朴素 O(nm²) 枚举与基于单调栈的 O(nm) 线性解法，并给出可直接运行的 C++ 实现。读完本文，你将掌握利用"最近 1 位置数组 d[i][j] + 单调栈求左右边界"的完整推导过程与工程实现，并能将其推广到直方图最大矩形等同类问题。

问题定义

给定一个包含n行、m列的矩阵，请找出其中全为 0 的最大子矩阵。这里的子矩阵指矩阵中的任意矩形区域，其四个边界与原矩阵的边界平行。

为了方便起见，本文将矩阵中的所有非零元素统一视为1，于是问题等价于：在只包含 0 与 1 的矩阵中，寻找面积最大的、不含任何 1 的矩形区域。

本文内容位于仓库的 src/dynamic_programming/zero_matrix.md，并被收录于 src/navigation.md 的 Dynamic Programming → Tasks 分类之下，属于动态规划专题中的经典任务型问题。

第一步：辅助动态规划数组d[i][j]

算法的第一步是计算一个辅助矩阵d[i][j]，其含义为：在j这一列中，位于元素a[i][j]上方的、距离最近的那个值为1的行号。

更形式化地说，d[i][j]是满足以下条件的最大的行号k（0 <= k <= i - 1）：在第j列的第k行存在一个值为1的元素。若上方没有 1，则取-1（表示可以从矩阵上边界开始延伸）。

由于我们按从上到下、从左到右的顺序遍历矩阵，当处理到第i行时，上一行的信息已经全部已知，因此只需要在遇到值为1的元素时更新当前列的记录即可。进一步地，后续算法是按行逐行处理的，某一时刻只需要当前行的信息，所以完全可以用一维数组d[j]（j = 0 ... m-1）来滚动维护，而不必保存整个二维矩阵d[i][j]。

对应的 C++ 初始化代码如下：

vector<int> d(m, -1); for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == 1) { d[j] = i; } } }

这段代码的直观理解是：d[j]记录的是"当前扫描到第i行时，第j列最近一次出现 1 的行号"。初始化为-1表示该列上方尚未出现过 1。

第二步：求解最大全零子矩阵

从朴素 O(nm²) 到线性

得到辅助数组后，一个直接的思路是：枚举每一行作为子矩阵的底边，再枚举所有可能的左右边界（左边列与右边列），复杂度为 O(nm²)。底边固定为当前行i后，利用d[i][j]即可确定顶边的位置。

但我们可以做得更好。一个关键观察是：任何最大的全零子矩阵，其四条边一定都被值为 1 的元素"挡住"——否则该子矩阵还可以继续向外扩展而增大面积。因此，最优答案一定不会被漏掉，如果我们采用如下策略：

对于第i行中的每个单元格j（把它当作潜在的全零子矩阵底边所在列），将d[i][j]视为当前全零子矩阵的顶边位置，剩下的任务就是确定最优的左右边界——即把以第j列为"锚点"的零子矩阵尽可能地往左、往右推到底。

左右边界k1与k2的定义

往左推到极限意味着：寻找一个索引k1，满足d[i][k1] > d[i][j]，并且k1是所有满足该条件的索引中、位于j左侧且距离j最近的那一个。

为什么d[i][k1] > d[i][j]就能"截断"？因为第k1列在第i行之上存在一个比当前顶边更低（行号更大、更靠近当前行）的 1，这个 1 会阻止零子矩阵向左扩展到第k1列。于是k1 + 1就是该全零子矩阵的左边界列号。如果左侧不存在这样的索引，则令k1 = -1，表示零子矩阵可以一直向左延伸到矩阵的左边框。

对称地，k2定义为：位于j右侧、距离j最近且满足d[i][k2] > d[i][j]的索引；若不存在则令k2 = m，表示可以向右延伸到矩阵右边框。

一旦高效求出k1与k2，以第j列为锚点、第i行为底边的最大全零子矩阵的信息就完全确定了，其面积为：

面积 = (i - d[i][j]) * (k2 - k1 - 1)

其中(i - d[i][j])是子矩阵的高（行跨度），(k2 - k1 - 1)是宽（列跨度）。

用单调栈在 O(1) 平均时间内求k1与k2

关键问题转化为：在固定第i行的情况下，如何对每个j高效地求出k1与k2。答案是利用单调栈，平均每个查询 O(1)。

先看k1的求法，结果保存到数组d1[j]（即原文档中的d1[i][j]的滚动一维形式）：

• 从左到右扫描当前行的所有列j；
• 栈中只保留那些d[列]严格大于当前d[j]的列；
• 当从列j走向下一列时，需要更新栈内容：若栈顶元素不满足条件（即d[栈顶] <= d[j]），则不断弹出栈顶；
• 之所以只需从栈顶弹出即可，是因为栈内保存的列的d值是严格递增的（栈底到栈顶的d值序列单调递增），任何不满足条件的元素必然位于栈顶附近；
• 处理完成后，d1[j]就等于当前栈顶元素（若栈为空则为-1），随后把j压入栈中。

d2[j]（用于求k2）的求法完全对称，只需从右到左扫描列，且栈空时取m。

为什么整体复杂度是线性的？因为每一行恰好有m个列索引被压入栈中，而每个元素最多被弹出一次，弹出总次数不会超过压入次数，因此每行的摊还复杂度为 O(m)，全部n行合计 O(nm)。

完整实现

以下是仓库文档中给出的完整 C++ 实现（可直接复制编译运行）：

int zero_matrix(vector<vector<int>> a) { int n = a.size(); int m = a[0].size(); int ans = 0; vector<int> d(m, -1), d1(m), d2(m); stack<int> st; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (a[i][j] == 1) d[j] = i; } for (int j = 0; j < m; ++j) { while (!st.empty() && d[st.top()] <= d[j]) st.pop(); d1[j] = st.empty() ? -1 : st.top(); st.push(j); } while (!st.empty()) st.pop(); for (int j = m - 1; j >= 0; --j) { while (!st.empty() && d[st.top()] <= d[j]) st.pop(); d2[j] = st.empty() ? m : st.top(); st.push(j); } while (!st.empty()) st.pop(); for (int j = 0; j < m; ++j) ans = max(ans, (i - d[j]) * (d2[j] - d1[j] - 1)); } return ans; }

对实现要点逐行说明：

• d(m, -1)滚动维护"本列最近一次出现 1 的行号"，初始-1表示尚未出现；
• 每处理一行，先用第一重循环更新d（把本行值为 1 的位置记录为当前行号i）；
• 第二重循环从左到右用单调栈求出每个j的d1[j]（左侧最近"阻隔 1"所在列，或-1）；
• 清空栈后，第三重循环从右到左对称地求出d2[j]（右侧最近"阻隔 1"所在列，或m）；
• 最后一重循环对每个j以(i - d[j]) * (d2[j] - d1[j] - 1)更新答案ans。

需要特别注意栈的比较条件d[st.top()] <= d[j]使用的是小于等于就弹出，这保证了栈中从底到顶的d值严格递增，从而栈顶元素就是满足d[栈顶列] > d[j]的最近一列。

复杂度与空间分析

• 时间复杂度：O(nm)。每一步：更新d为 O(m)；两次单调栈扫描各为 O(m)（每个元素入栈一次、出栈至多一次，摊还线性）；更新答案为 O(m)。全部n行合计 O(nm)，远优于朴素的 O(nm²) 枚举。
• 空间复杂度：O(m)（不计入输入矩阵a本身）。只额外使用了d、d1、d2三个长度m的数组和一个单调栈，栈内至多存放m个列索引。

方法推广：直方图最大矩形与"按行累计"技巧

该算法的核心结构可以被提炼为一种通用的子矩形查找范式，值得单独总结：

1. 按行滚动维护辅助信息：d[j]记录当前列上方最近一个 1 的位置，等价于把每一列看成一段"从底边向上延伸的连续 0 的高度"，即把矩阵的每一行转化为一个直方图问题——i - d[j]就是以第i行为底时第j列可向上延伸的连续 0 的高度。
2. 单调栈求左右边界：在直方图上求最大矩形（LeetCode 84 题的经典模型），正是对每个柱子求出左右两侧第一个高度更矮的柱子，其做法与本算法中求k1、k2的栈操作完全同构。
3. 摊还线性：栈中元素"一次入栈、至多一次出栈"的单调性保证，使得每行的处理摊还 O(m)。

因此，理解本算法后，你实际上同时掌握了"直方图最大矩形"这一更基础模型的线性解法，两者可以互相印证。本仓库中同样位于动态规划专题下的其他任务型文章，如 profile-dynamics.md（破碎轮廓上的 DP / "Parquet" 问题），展示了另一类在网格上做动态规划的思考方式，可作为对照学习。

小结

本文围绕 cp-algorithms 仓库的 zero_matrix.md 文档，完整呈现了"最大全零子矩阵"问题的求解链：从朴素 O(nm²) 枚举出发，借助"辅助数组d[j]+ 单调栈求最近阻隔列"的观察，将算法优化到 O(nm) 时间、O(m) 空间。文中的完整 C++ 实现 源码位置 可直接移植到竞赛代码或工程实践中，其单调栈思想同样适用于直方图最大矩形、最大 1 矩形（1 与 0 互换即可）等系列经典问题。

• 文档
• 教程
• 知识库