文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载导读在计算机视觉、图像处理与算法竞赛中常需要在 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]是满足以下条件的最大的行号k0 k i - 1在第j列的第k行存在一个值为1的元素。若上方没有 1则取-1表示可以从矩阵上边界开始延伸。由于我们按从上到下、从左到右的顺序遍历矩阵当处理到第i行时上一行的信息已经全部已知因此只需要在遇到值为1的元素时更新当前列的记录即可。进一步地后续算法是按行逐行处理的某一时刻只需要当前行的信息所以完全可以用一维数组d[j]j 0 ... m-1来滚动维护而不必保存整个二维矩阵d[i][j]。对应的 C 初始化代码如下vectorint 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(vectorvectorint a) { int n a.size(); int m a[0].size(); int ans 0; vectorint d(m, -1), d1(m), d2(m); stackint 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个列索引。方法推广直方图最大矩形与按行累计技巧该算法的核心结构可以被提炼为一种通用的子矩形查找范式值得单独总结按行滚动维护辅助信息d[j]记录当前列上方最近一个 1 的位置等价于把每一列看成一段从底边向上延伸的连续 0 的高度即把矩阵的每一行转化为一个直方图问题——i - d[j]就是以第i行为底时第j列可向上延伸的连续 0 的高度。单调栈求左右边界在直方图上求最大矩形LeetCode 84 题的经典模型正是对每个柱子求出左右两侧第一个高度更矮的柱子其做法与本算法中求k1、k2的栈操作完全同构。摊还线性栈中元素一次入栈、至多一次出栈的单调性保证使得每行的处理摊还 O(m)。因此理解本算法后你实际上同时掌握了直方图最大矩形这一更基础模型的线性解法两者可以互相印证。本仓库中同样位于动态规划专题下的其他任务型文章如 profile-dynamics.md破碎轮廓上的 DP / Parquet 问题展示了另一类在网格上做动态规划的思考方式可作为对照学习。小结本文围绕 cp-algorithms 仓库的 zero_matrix.md 文档完整呈现了最大全零子矩阵问题的求解链从朴素 O(nm²) 枚举出发借助辅助数组d[j] 单调栈求最近阻隔列的观察将算法优化到 O(nm) 时间、O(m) 空间。文中的完整 C 实现 源码位置 可直接移植到竞赛代码或工程实践中其单调栈思想同样适用于直方图最大矩形、最大 1 矩形1 与 0 互换即可等系列经典问题。赞分享文档教程知识库【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址https://gitcode.com/GitHub_Trending/cp/cp-algorithms点击查看免费下载相关推荐Kretes部署指南3种简单方法将你的Deno应用上线生产环境Kretes部署指南3种简单方法将你的Deno应用上线生产环境 Kretes是专为TypeScript和Deno设计的编程环境本指南将介绍3种简单方法帮助你如何快速切换 AI 大模型Atomic Agents 多提供商切换完全指南OpenAI、Claude、Gemini 与 Ollama 本地模型自由互换如何快速切换 AI 大模型Atomic Agents 多提供商切换完全指南OpenAI、Claude、Gemini 与 Ollama 本地模型自由互换 AtAI AgentAgent 框架MCP 服务后端矩阵置零LeetCode 0073题解AlgoNote 仓库中 O(1) 空间原地算法实战矩阵置零LeetCode 0073题解AlgoNote 仓库中 O 1 空间原地算法实战 本篇题解聚焦 LeetCode 0073「矩阵置零」Set M教程文档知识库上一篇基于RuoYi-Vue构建企业级文档管理系统的架构设计与系统集成方案下一篇LX Music Desktop3大核心功能解锁免费开源音乐播放器的终极体验创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考