LeetCode 85 最大矩形题解单调栈 柱状图降维法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文讲解 LeetCode 85「最大矩形」的完整解题思路给定一个仅包含0和1的二维二进制矩阵找出只包含1的最大矩形并返回其面积。核心技巧是将二维矩阵逐行累加压缩为一维柱状图heights 数组从而把问题规约到经典的 84. 柱状图中最大的矩形再用单调栈在 O(M × N) 时间内求解。读完本文你将掌握「二维问题降维成一维」的建模方法、单调栈的哨兵技巧以及一套可复用的矩形面积求解 API。题目描述与示例给定一个仅包含0和1的二维二进制矩阵找出只包含1的最大矩形并返回其面积。示例输入如下矩阵[ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ]输出6即由第二、三行与第三、四、五列交叉形成的2 × 3矩形区域。前置知识单调栈本题的前置知识是单调栈。单调栈是一种特殊的栈它要求栈中的元素始终保持单调递增或单调递减。以[a, b, c]表示一个栈左侧为栈底、右侧为栈顶如果出栈的元素是单调增的那就是单调递增栈反之则是单调递减栈。例如[1, 2, 3, 4]是单调递减栈出栈顺序 4, 3, 2, 1[3, 2, 1]是单调递增栈[1, 3, 2]不是合法的单调栈。单调栈天然适合求解「下一个大于 xxx」或「下一个小于 xxx」这类问题。当需要求解在其之后第一个小于其本身的位置时可以用单调栈在 O(N) 时间内一次遍历完成如果压栈之后仍然可以保持单调性那么直接压否则先弹出栈顶元素直到压入之后可以保持单调性。其原理是被弹出的元素都大于或小于当前元素且由于栈是单调的当前元素就是被弹出元素之后第一个更小或更大的元素。关于单调栈的详细原理、伪代码模板与 Python / JavaScript 双语言实现可以参考本仓库的 单调栈专题。哨兵法简化边界处理的通用技巧单调栈题目的一个常见坑点是遍历结束后栈中仍残留未参与计算的元素。此时可以引入哨兵法在数组末尾添加一个足够小或足够大的哨兵值强制所有元素出栈从而统一算法逻辑、减少边界判断。这一技巧在本题和 84 题中都有体现是单调栈解题的标准优化手段。核心思路把二维矩阵压缩成一维柱状图回到本题。一个直观但不可行的做法是暴力枚举所有可能的矩形子区域检查其中是否全为1复杂度高达 O(M² × N²)。正确的做法是逐行扫描、动态维护一维高度数组。拿题目给的例子[ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ]从第一行开始逐行处理heights[j]表示以当前行为底边、第 j 列向上连续1的个数第 1 行处理完[1, 0, 1, 0, 0]第 2 行处理完[2, 0, 2, 1, 1]第三列向上连续两个 1故为 2第 3 行处理完[3, 1, 3, 2, 2]第 4 行处理完[4, 0, 0, 3, 0]遇到0时高度清零因为矩形必须连续。这样每一行得到的heights数组恰好就是 84. 柱状图中最大的矩形 中柱状图的高度数组。原二维问题就此被规约成了 M 次一维柱状图最大矩形求解只需对每一行调用一次 84 题的解即可最终答案取所有行的最大值。深入 84 题柱状图中最大的矩形的多种解法84 题求解的柱状图最大矩形面积是本题的基石仓库题解中给出了四种递进的方法1. 暴力枚举 - 左右端点法TLE用双层循环枚举左右端点区间高度取最小值面积 (右端点 - 左端点 1) × 最小高度。时间复杂度 O(N²)。2. 暴力枚举 - 中心扩展法TLE对每个柱子 i分别向左向右找到第一个高度小于它的柱子索引 p 和 q则(q - p - 1) × heights[i]就是以 i 为最低点的最大矩形面积。原问题转化为求所有f(i)的最大值。时间复杂度 O(N²)。3. 优化中心扩展法Accepted利用l[i]、r[i]数组做跳跃式查找j l[j]/j r[j]将内层循环摊还到 O(1)整体 O(N)。4. 单调栈Accepted本题采用的解法从左到右遍历柱子用一个单调递减栈维护「第一个高度小于当前柱子的位置」。对于栈顶元素其右边第一个小于它的柱子就是当前遍历到的柱子左边第一个小于它的柱子就是栈中下一个要弹出的元素于是以当前栈顶为最小柱子的面积为heights[栈顶] × (当前索引 - 栈中下一个元素索引 - 1)。每个元素最多入栈出栈一次时间、空间复杂度均为 O(N)。84 题单调栈代码含双哨兵仓库中 84 题给出的单调栈解法如下它在heights首尾各添加了一个哨兵0class Solution: def largestRectangleArea(self, heights: List[int]) - int: n, heights, st, ans len(heights), [0] heights [0], [], 0 for i in range(n 2): while st and heights[st[-1]] heights[i]: ans max(ans, heights[st.pop(-1)] * (i - st[-1] - 1)) st.append(i) return ans这里两个哨兵各有作用详见 84 题题解末尾的哨兵遍历结束后强制把栈清空防止栈中残留未参与运算的数据首部的哨兵当栈顶被弹出后st[-1]不会越界若没有首部哨兵弹出最后一个元素后取st[-1]会索引越界。仓库还给出了等价的 C 实现帮助读者对照理解指针与索引的换算关系。85 题完整代码与逐行解析理解了 84 题后85 题的代码就非常自然外层逐行维护 heights内层调用 84 题的 API 计算当前行的最大矩形面积。原题解给出的 Python 代码如下class Solution: def largestRectangleArea(self, heights: List[int]) - int: n, heights, st, ans len(heights), [0] heights [0], [], 0 for i in range(n 2): while st and heights[st[-1]] heights[i]: ans max(ans, heights[st.pop(-1)] * (i - st[-1] - 1)) st.append(i) return ans def maximalRectangle(self, matrix: List[List[str]]) - int: m len(matrix) if m 0: return 0 n len(matrix[0]) heights [0] * n ans 0 for i in range(m): for j in range(n): if matrix[i][j] 0: heights[j] 0 else: heights[j] 1 ans max(ans, self.largestRectangleArea(heights)) return ans逐行拆解maximalRectangle的执行流程空矩阵防护m len(matrix)若m 0直接返回0避免对空输入取matrix[0]越界初始化高度数组heights [0] * nn 为列数每一轮都会以当前行作为柱状图的底边逐行扫描更新高度遍历当前行每一列若matrix[i][j] 0则高度清零矩形不能跨过 0 断开否则heights[j] 1在上一行基础上累加体现「向上连续 1 的个数」调用一维求解器ans max(ans, self.largestRectangleArea(heights))用 84 题的单调栈解法求当前行的最大矩形面积并更新全局答案。注意输入矩阵的元素是字符串1/0而非整数 1 / 0代码中比较时使用了字符串字面量0这是 LeetCode 输入格式的常见细节不要写错。复杂度分析时间复杂度O(M × N)。外层遍历 M 行内层每行更新 heights 花费 O(N)每行调用一次 84 题的单调栈算法其复杂度为 O(N)。合计 O(M × N)若 M N可转置矩阵使列数更小进一步降低常数。空间复杂度O(N)。仅需一维heights数组长度 N和单调栈最多压入 N 个索引没有使用任何二维辅助空间相比纯 DP 解法空间开销更优。正确性论证本算法的正确性由两部分保证降维的正确性任意一个只含1的矩形其底边必落在矩阵的某一些行上。若取矩形的底边所在行作为扫描行 i则矩形各列在 i 行处向上连续1的个数必然不小于该矩形的高度因为矩形内部全是 1因此该矩形会被heights数组完整捕获且其面积一定不超过第 i 行柱状图的最大矩形面积。反过来柱状图任意一个矩形都对应矩阵中一个全 1 矩形。二者最大面积相等。单调栈的正确性84 题单调栈求解中每个柱子作为「最低点」时其左右第一个更矮柱子的位置唯一确定了它能撑起的最大矩形边界遍历所有柱子取最大值即为全局最大。该结论在 84 题题解 中通过中心扩展法的等价性做了严格论证。边界情况与易错点空矩阵matrix为空列表时需直接返回 0代码已处理单行/单列矩阵heights长度为 1 时哨兵[0, h, 0]使得循环能正确处理单个柱子的面积连续0中断遇到0必须将heights[j]清零否则会把不连续的高度错误累加导致算出跨越0的非法矩形字符串 vs 整数题目输入为字符矩阵判断时应使用 0而不是 0哨兵不可省略去掉首部哨兵会在弹栈后出现st[-1]越界去掉末尾哨兵会在遍历结束后遗漏未出栈柱子对应的候选面积。与其他相关题目的联系本仓库中与该题强相关的题目与专题资源包括84. 柱状图中最大的矩形本题的降维目标四种解法递进强烈建议先掌握221. 最大正方形同样是二维 01 矩阵求最大图形面积但它限制为正方形因此适合用动态规划dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1求解时间复杂度 O(M × N)、空间 O(M × N)与 85 题形成「DP 解正方形 / 单调栈解矩形」的对比学习组合42. 接雨水同样是柱状图上的经典问题可进一步巩固单调栈、双指针的应用单调栈专题系统讲解单调栈原理、适用场景与通用模板。建议的练习路径先刷 84 题掌握单调栈求柱状图最大矩形 → 再看 85 题体会二维降维 → 最后用 221 题对比 DP 与单调栈两种范式的适用边界。总结最大矩形的核心套路可以概括为三步降维逐行扫描把二维 01 矩阵维护成一维heights数组遇 0 清零、遇 1 累加复用把问题规约到 84 题「柱状图中最大的矩形」直接复用单调栈求解 API取最值每一行求解后更新全局最大面积。这种「把一个复杂问题规约成若干次已知经典问题」的建模思路在算法面试中非常高频值得反复揣摩。掌握单调栈 哨兵的写法模板85 题便不再需要死记硬背而是可以现场推导。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
LeetCode 85 最大矩形题解：单调栈 + 柱状图降维法
LeetCode 85 最大矩形题解单调栈 柱状图降维法【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文讲解 LeetCode 85「最大矩形」的完整解题思路给定一个仅包含0和1的二维二进制矩阵找出只包含1的最大矩形并返回其面积。核心技巧是将二维矩阵逐行累加压缩为一维柱状图heights 数组从而把问题规约到经典的 84. 柱状图中最大的矩形再用单调栈在 O(M × N) 时间内求解。读完本文你将掌握「二维问题降维成一维」的建模方法、单调栈的哨兵技巧以及一套可复用的矩形面积求解 API。题目描述与示例给定一个仅包含0和1的二维二进制矩阵找出只包含1的最大矩形并返回其面积。示例输入如下矩阵[ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ]输出6即由第二、三行与第三、四、五列交叉形成的2 × 3矩形区域。前置知识单调栈本题的前置知识是单调栈。单调栈是一种特殊的栈它要求栈中的元素始终保持单调递增或单调递减。以[a, b, c]表示一个栈左侧为栈底、右侧为栈顶如果出栈的元素是单调增的那就是单调递增栈反之则是单调递减栈。例如[1, 2, 3, 4]是单调递减栈出栈顺序 4, 3, 2, 1[3, 2, 1]是单调递增栈[1, 3, 2]不是合法的单调栈。单调栈天然适合求解「下一个大于 xxx」或「下一个小于 xxx」这类问题。当需要求解在其之后第一个小于其本身的位置时可以用单调栈在 O(N) 时间内一次遍历完成如果压栈之后仍然可以保持单调性那么直接压否则先弹出栈顶元素直到压入之后可以保持单调性。其原理是被弹出的元素都大于或小于当前元素且由于栈是单调的当前元素就是被弹出元素之后第一个更小或更大的元素。关于单调栈的详细原理、伪代码模板与 Python / JavaScript 双语言实现可以参考本仓库的 单调栈专题。哨兵法简化边界处理的通用技巧单调栈题目的一个常见坑点是遍历结束后栈中仍残留未参与计算的元素。此时可以引入哨兵法在数组末尾添加一个足够小或足够大的哨兵值强制所有元素出栈从而统一算法逻辑、减少边界判断。这一技巧在本题和 84 题中都有体现是单调栈解题的标准优化手段。核心思路把二维矩阵压缩成一维柱状图回到本题。一个直观但不可行的做法是暴力枚举所有可能的矩形子区域检查其中是否全为1复杂度高达 O(M² × N²)。正确的做法是逐行扫描、动态维护一维高度数组。拿题目给的例子[ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ]从第一行开始逐行处理heights[j]表示以当前行为底边、第 j 列向上连续1的个数第 1 行处理完[1, 0, 1, 0, 0]第 2 行处理完[2, 0, 2, 1, 1]第三列向上连续两个 1故为 2第 3 行处理完[3, 1, 3, 2, 2]第 4 行处理完[4, 0, 0, 3, 0]遇到0时高度清零因为矩形必须连续。这样每一行得到的heights数组恰好就是 84. 柱状图中最大的矩形 中柱状图的高度数组。原二维问题就此被规约成了 M 次一维柱状图最大矩形求解只需对每一行调用一次 84 题的解即可最终答案取所有行的最大值。深入 84 题柱状图中最大的矩形的多种解法84 题求解的柱状图最大矩形面积是本题的基石仓库题解中给出了四种递进的方法1. 暴力枚举 - 左右端点法TLE用双层循环枚举左右端点区间高度取最小值面积 (右端点 - 左端点 1) × 最小高度。时间复杂度 O(N²)。2. 暴力枚举 - 中心扩展法TLE对每个柱子 i分别向左向右找到第一个高度小于它的柱子索引 p 和 q则(q - p - 1) × heights[i]就是以 i 为最低点的最大矩形面积。原问题转化为求所有f(i)的最大值。时间复杂度 O(N²)。3. 优化中心扩展法Accepted利用l[i]、r[i]数组做跳跃式查找j l[j]/j r[j]将内层循环摊还到 O(1)整体 O(N)。4. 单调栈Accepted本题采用的解法从左到右遍历柱子用一个单调递减栈维护「第一个高度小于当前柱子的位置」。对于栈顶元素其右边第一个小于它的柱子就是当前遍历到的柱子左边第一个小于它的柱子就是栈中下一个要弹出的元素于是以当前栈顶为最小柱子的面积为heights[栈顶] × (当前索引 - 栈中下一个元素索引 - 1)。每个元素最多入栈出栈一次时间、空间复杂度均为 O(N)。84 题单调栈代码含双哨兵仓库中 84 题给出的单调栈解法如下它在heights首尾各添加了一个哨兵0class Solution: def largestRectangleArea(self, heights: List[int]) - int: n, heights, st, ans len(heights), [0] heights [0], [], 0 for i in range(n 2): while st and heights[st[-1]] heights[i]: ans max(ans, heights[st.pop(-1)] * (i - st[-1] - 1)) st.append(i) return ans这里两个哨兵各有作用详见 84 题题解末尾的哨兵遍历结束后强制把栈清空防止栈中残留未参与运算的数据首部的哨兵当栈顶被弹出后st[-1]不会越界若没有首部哨兵弹出最后一个元素后取st[-1]会索引越界。仓库还给出了等价的 C 实现帮助读者对照理解指针与索引的换算关系。85 题完整代码与逐行解析理解了 84 题后85 题的代码就非常自然外层逐行维护 heights内层调用 84 题的 API 计算当前行的最大矩形面积。原题解给出的 Python 代码如下class Solution: def largestRectangleArea(self, heights: List[int]) - int: n, heights, st, ans len(heights), [0] heights [0], [], 0 for i in range(n 2): while st and heights[st[-1]] heights[i]: ans max(ans, heights[st.pop(-1)] * (i - st[-1] - 1)) st.append(i) return ans def maximalRectangle(self, matrix: List[List[str]]) - int: m len(matrix) if m 0: return 0 n len(matrix[0]) heights [0] * n ans 0 for i in range(m): for j in range(n): if matrix[i][j] 0: heights[j] 0 else: heights[j] 1 ans max(ans, self.largestRectangleArea(heights)) return ans逐行拆解maximalRectangle的执行流程空矩阵防护m len(matrix)若m 0直接返回0避免对空输入取matrix[0]越界初始化高度数组heights [0] * nn 为列数每一轮都会以当前行作为柱状图的底边逐行扫描更新高度遍历当前行每一列若matrix[i][j] 0则高度清零矩形不能跨过 0 断开否则heights[j] 1在上一行基础上累加体现「向上连续 1 的个数」调用一维求解器ans max(ans, self.largestRectangleArea(heights))用 84 题的单调栈解法求当前行的最大矩形面积并更新全局答案。注意输入矩阵的元素是字符串1/0而非整数 1 / 0代码中比较时使用了字符串字面量0这是 LeetCode 输入格式的常见细节不要写错。复杂度分析时间复杂度O(M × N)。外层遍历 M 行内层每行更新 heights 花费 O(N)每行调用一次 84 题的单调栈算法其复杂度为 O(N)。合计 O(M × N)若 M N可转置矩阵使列数更小进一步降低常数。空间复杂度O(N)。仅需一维heights数组长度 N和单调栈最多压入 N 个索引没有使用任何二维辅助空间相比纯 DP 解法空间开销更优。正确性论证本算法的正确性由两部分保证降维的正确性任意一个只含1的矩形其底边必落在矩阵的某一些行上。若取矩形的底边所在行作为扫描行 i则矩形各列在 i 行处向上连续1的个数必然不小于该矩形的高度因为矩形内部全是 1因此该矩形会被heights数组完整捕获且其面积一定不超过第 i 行柱状图的最大矩形面积。反过来柱状图任意一个矩形都对应矩阵中一个全 1 矩形。二者最大面积相等。单调栈的正确性84 题单调栈求解中每个柱子作为「最低点」时其左右第一个更矮柱子的位置唯一确定了它能撑起的最大矩形边界遍历所有柱子取最大值即为全局最大。该结论在 84 题题解 中通过中心扩展法的等价性做了严格论证。边界情况与易错点空矩阵matrix为空列表时需直接返回 0代码已处理单行/单列矩阵heights长度为 1 时哨兵[0, h, 0]使得循环能正确处理单个柱子的面积连续0中断遇到0必须将heights[j]清零否则会把不连续的高度错误累加导致算出跨越0的非法矩形字符串 vs 整数题目输入为字符矩阵判断时应使用 0而不是 0哨兵不可省略去掉首部哨兵会在弹栈后出现st[-1]越界去掉末尾哨兵会在遍历结束后遗漏未出栈柱子对应的候选面积。与其他相关题目的联系本仓库中与该题强相关的题目与专题资源包括84. 柱状图中最大的矩形本题的降维目标四种解法递进强烈建议先掌握221. 最大正方形同样是二维 01 矩阵求最大图形面积但它限制为正方形因此适合用动态规划dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1求解时间复杂度 O(M × N)、空间 O(M × N)与 85 题形成「DP 解正方形 / 单调栈解矩形」的对比学习组合42. 接雨水同样是柱状图上的经典问题可进一步巩固单调栈、双指针的应用单调栈专题系统讲解单调栈原理、适用场景与通用模板。建议的练习路径先刷 84 题掌握单调栈求柱状图最大矩形 → 再看 85 题体会二维降维 → 最后用 221 题对比 DP 与单调栈两种范式的适用边界。总结最大矩形的核心套路可以概括为三步降维逐行扫描把二维 01 矩阵维护成一维heights数组遇 0 清零、遇 1 累加复用把问题规约到 84 题「柱状图中最大的矩形」直接复用单调栈求解 API取最值每一行求解后更新全局最大面积。这种「把一个复杂问题规约成若干次已知经典问题」的建模思路在算法面试中非常高频值得反复揣摩。掌握单调栈 哨兵的写法模板85 题便不再需要死记硬背而是可以现场推导。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考