1. 题目拆解：最大矩形到底在考什么
1.1 题意速览与输入输出
先花三十秒把题看清楚。LeetCode 85题"最大矩形"给的是一张二维的二进制矩阵，里面每个格子要么是0要么是1，要求在这个矩阵里找出一个“只包含1”的矩形区域，让它的面积最大，最后返回这个最大面积。
举个例子，矩阵长这样：
1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0肉眼扫一下，最大的全1矩形是第二行到第三行、第三列到第五列围出来的那块，宽度3、高度2，面积等于6。如果用代码去算，标准答案也是6。
注意几个细节：矩阵的宽和高都可能为0；格子里的"1"是字符，不是数字；返回的是面积值不是坐标。这些都是提交时容易翻车的点，后面我专门列一节讲。
1.2 为什么这题值得花时间
如果你刷过LeetCode热榜100题，大概率见过这道题。它经常和84题"柱状图中最大的矩形"绑在一起出现，85题本质上就是84题套上了一层二维的外衣。面试里出现频率不低，尤其是大厂笔试和算法轮，因为它考察的不是你背没背过模板，而是能不能把一个陌生问题拆成熟悉问题。
另外这题的解法思路很有迁移价值。单调栈、动态规划、逐行累积高度，这三个技术点每一个都能单独出题，85题把它们串在了一个完整场景里。刷透这一题，等于是把三个知识点连着复习了一遍，性价比非常高。
我自己的感受是：这题第一眼看上去特别唬人，因为“二维矩阵里找最大矩形”这个描述太开放了，新手很容易直接想到暴力枚举左上角和右下角，然后被 O(n² × m²) 的复杂度劝退。但如果你已经刷过84题，就会敏锐地发现：每一行往上数连续1的个数，其实就是一个柱状图的高度数组。于是问题就变成了“逐行调用84题的解法”。
2. 核心思路：把二维问题压成一维
2.1 高度数组的累积逻辑
先理解一个关键动作：从上到下扫描矩阵的每一行，同时维护一个一维数组 heights，heights[j] 表示“以当前行为底边、第 j 列往上连续有多少个1”。
怎么维护？逐行更新就行：
- 如果当前行的第 j 列是 '1'，那 heights[j] 就在上一行的基础上加1；
- 如果当前行的第 j 列是 '0'，那 heights[j] 直接归零，因为一旦出现0，往上再多的1也被拦腰截断，这个位置不能再向上延伸了。
举上面的例子，前三行算下来，heights 数组的变化是这样：
第一行结束：[1, 0, 1, 0, 0]
第二行结束：[2, 0, 2, 1, 1]
第三行结束：[3, 1, 3, 2, 2]
到第三行的时候，heights 数组就是[3,1,3,2,2]。这意味着什么？意味着在这一个高度数组上跑一遍“柱状图中最大矩形”的算法，求出来的最大矩形面积，就对应着原矩阵里所有“底边落在第三行、向上连续全1”的矩形里的最大值。而原矩阵的最大矩形，底边一定落在某一行上，所以只要把每一行都当底边算一遍，取全局最大，答案就出来了。
这个转换是整个题目的灵魂。把一个看不清全局的二维问题，拆成一组一维柱状图，每一步只关心“当前底边之上有多高”，信息一点没丢，计算却简单了一个维度。
2.2 为什么能跳行计算——84题的联动
LeetCode 84题给的是一个一维数组，每个元素代表一根柱子的高度，要求这堆柱子里能框出的最大矩形面积。经典解法是用单调栈，在 O(n) 时间内搞定。
85题的做法就是：把矩阵的每一行当作84题的输入，逐行调用。所以如果你84题已经吃透了，85题只是多了一个“逐行构建高度数组”的预处理步骤。
有人会问：为什么不直接对每个格子向左、向右扩展边界，那样不也能算矩形吗？能做，而且这是另一种解法，叫“枚举左右边界+高度数组”，复杂度是 O(m×n²)。但既然我们有 O(m×n) 的单调栈方案，就没必要退回去写平方级算法。
还有人会问：能不能用动态规划直接记录“以某个格子为右下角的最大矩形”？理论上可以，但状态定义比想象中麻烦。因为矩形面积由高度和宽度共同决定，单纯记“到当前格子左边连续1的个数”和“上方连续1的个数”还不够，你还要枚举宽度，最终复杂度还是平方级。所以单调栈方案在这题里是综合最优的主流解法。
2.3 暴力回溯法作为参照系
在写单调栈之前，可以先在心里过一遍暴力法，方便对比复杂度。最朴素的做法是枚举矩形的左上角和右下角，然后检查中间区域是否全为1，这需要 O(m² × n² × 检查代价)，妥妥的不可接受。好一点的暴力是：枚举每一行作为矩形的顶边，然后向下扩展底边，同时维护每一列在这段行区间里是否全是1，再去求连续1区间的最大长度作为宽度。这样是 O(m²×n)，能过小数据，但大数据会超时。
我建议初学者把这种暴力思路作为参照系：先想清楚“枚举顶边和底边再扩展宽度”逻辑上为什么正确，再去看单调栈怎么把其中重复计算的部分优化掉。这样你对算法的理解会深一层，而不是单纯背模板。
3. 单调栈解法：完整实现与逐行注释
3.1 单调栈的工作原理
先说核心数据结构——单调栈。它维护的是一个索引栈，栈里的索引对应的柱高保持严格递增（或者非递减，看你处理边界的方式）。它的作用是：当新柱子高度小于栈顶柱高时，说明栈顶那根柱子的右边界已经确定了，这时候可以弹出它，并计算以它为高度的最大矩形面积。
这里有一个新手最容易绕晕的点：弹出一个柱子时，它的左右边界到底是什么？
- 右边界：就是当前扫描到的位置 i，因为这是第一个比它矮的柱子，矩形不可能再往右延伸。
- 左边界：弹出之后新的栈顶元素对应的位置，因为栈内索引递增，栈顶元素是左边第一个比它矮的柱子，矩形不可能再往左延伸。
所以宽度就是当前索引 - 左边界索引 - 1。如果栈空了，说明左边没有比它矮的柱子，宽度就是当前索引本身。
这个逻辑听起来绕，画个图马上清楚。比如柱高数组[2,1,5,6,2,3]，扫到索引4的柱子高度2时，栈里存着[1,3]（索引1高度1，索引3高度6），索引4高度2比栈顶索引3高度6矮，于是弹出高度6，此时左边界是新的栈顶索引1，右边界是4，宽度就是4 - 1 - 1 = 2，面积6×2=12。对，这就是84题里那个最大面积12的由来。
3.2 Python 实现与逐行说明
把84题的单调栈函数单独抽出来，85题的主函数逐行构建高度数组并调用它。完整代码如下：
class Solution: def maximalRectangle(self, matrix: List[List[str]]) -> int: if not matrix or not matrix[0]: return 0 rows, cols = len(matrix), len(matrix[0]) heights = [0] * cols max_area = 0 for i in range(rows): # 1. 更新当前行的高度数组 for j in range(cols): if matrix[i][j] == '1': heights[j] += 1 else: heights[j] = 0 # 2. 计算当前高度数组的最大矩形面积 max_area = max(max_area, self.largest_rectangle_area(heights)) return max_area def largest_rectangle_area(self, heights: List[int]) -> int: # 哨兵：在末尾补一个0，保证所有柱子都能被弹出 heights.append(0) stack = [] area = 0 for i, h in enumerate(heights): while stack and heights[stack[-1]] > h: height = heights[stack.pop()] width = i if not stack else i - stack[-1] - 1 area = max(area, height * width) stack.append(i) # 还原数组，避免影响下一轮 heights.pop() return area讲几个容易被忽略的细节。
第一，主函数里更新高度数组用的是原地更新heights[j] += 1，而不是重新赋值。因为 heights 数组跨行复用，上一行的信息要保留下来累加。
第二，判断字符是 '1' 用的是引号括起来的字符，不是数字1。LeetCode 的矩阵输入元素是字符串，很多人在这里踩坑，写成了== 1，结果全矩阵都是0，答案永远是0。
第三，largest_rectangle_area函数最后补了一个0作为哨兵，这是84题的标准技巧。有了它，弹出的逻辑不用在循环外再单独处理一遍栈里剩余的柱子，代码更简洁，也不容易漏算。
第四，heights.pop()这一行很多人不写，导致下一轮调用时数组末尾多了一个0，后面的计算全部出错。单独调试时看起来没问题，丢到循环里就暴露问题了。
3.3 边界初始化与哨兵技巧
哨兵（sentinel）值是单调栈题里的常用手法。84题里末尾补0，是因为0一定是最矮的柱子，它会把栈里所有更高的柱子全部逼出来，这样循环结束后栈自动清空，不需要再写一段收尾代码。而主函数里为什么要heights = [0] * cols而不是[]？因为高度数组的长度必须等于列数，每个位置独立累积，如果初始为空列表，后面的heights[j] += 1就会报索引越界。
还有一种写法是把哨兵放在循环内部，比如用stack = [-1]技巧，让宽度计算统一成i - stack[-1] - 1。这个写法更炫，但对新手不够直观，我这边给出的是可读性优先的版本，面试讲思路时也更容易说清楚。
另外，如果你想追求极致性能，可以不用单独写84题的辅助函数，而是把单调栈逻辑直接嵌进主函数的行循环里，省去反复 append/pop 数组末尾的开销。不过刷题阶段没必要这么做，代码清晰更重要。
4. 复杂度分析与常见误区
4.1 时间与空间复杂度推导
时间上，外层循环遍历矩阵的每一行，是 O(m)。内层分成两部分：更新高度数组是 O(n)，调用单调栈函数也是 O(n)。关键是单调栈虽然内部有 while 循环，但每个索引最多入栈一次、出栈一次，所以均摊下来是 O(n)。整体复杂度就是 O(m×n)，也就是 O(矩阵元素总数)。
如果你写的是枚举左右边界+高度数组的版本，复杂度是 O(m×n²)，虽然也能跑对样例，但到数据量大时会超时。LeetCode 上矩阵最大能到200×200，m×n² 在最坏情况下是 200×40000 = 800万次，勉强能过；如果题面加强到1000×1000，800万就变成10亿次，直接崩。所以单调栈版本是必要的。
空间上，heights 数组长度 n，单调栈长度最多也是 n，所以空间复杂度 O(n)。如果你把单调栈逻辑嵌进主函数，连辅助函数的调用栈都省了，但空间复杂度不变。
4.2 五个高频踩坑点
我整理了一下实际操作中遇到的、以及帮别人看代码时常见的坑，按出现频率排个序。
第一，字符与数字混淆。matrix[i][j] 是字符串 '1' 不是整数1，判断条件写错的话整个算法输出恒为0，而且编辑器不会报错，肉眼调半天发现不了。建议在写代码前先打印一行matrix[0]确认类型。
第二，heights 数组没复位。有些人喜欢在循环里新建heights = [0] * cols而不是复用数组，这没问题，反而能避开末尾多0的隐患。但如果你在辅助函数里往 heights 末尾 append(0)，就一定要记得 pop 还原。这个 bug 特别隐蔽，因为单独测辅助函数是对的，只有跑完整用例才出错。
第三，单调栈里用值比较还是索引比较。我自己刚开始写的时候容易写成while stack and heights[i] < heights[stack[-1]]之后在循环体里想用 i 又发现 i 被修改了，搞得很乱。统一写法：栈里存索引，比较时通过索引取高度，循环变量 i 始终表示当前扫描位置，不要动不动修改它。
第四，宽度计算漏减1。弹出柱子时宽度是右边界 - 左边界 - 1，这个 -1 是左右两个端点都不算在内。我第一次写84题时漏了这个1，导致所有面积都偏大，还以为是矩形定义的问题。
第五，只更新 heights 但没重新算最大面积。有些新手会在所有行遍历完之后只算一次最大面积，忽略了面积取的是每一行底边对应的最大值，而不是最后一行的高度数组。你必须在每扫完一行之后立即更新 max_area。
4.3 Debug 技巧与测试用例
刷这题时我强烈建议准备一个本地调试脚本，打印每一轮的高度数组和当前最大面积，方便定位问题。比如上面那个矩阵，正确的中间输出应该是：
第1行后 heights = [1, 0, 1, 0, 0]，当前最大面积 = 1 第2行后 heights = [2, 0, 2, 1, 1]，当前最大面积 = 2 第3行后 heights = [3, 1, 3, 2, 2]，当前最大面积 = 6 第4行后 heights = [4, 0, 0, 3, 0]，当前最大面积 = 6如果你某一行输出对不上，就直接缩小范围，用2×2或3×3的小矩阵手动模拟一遍。注意 LeetCode 的输入矩阵每行是字符串，比如["10100","10111","11111","10010"]，在本地调试时可以直接用 Python 的 list 表示。
另一个好用的边界测试用例：matrix = [["0"]]，期望输出0，验证空矩阵以外的零矩阵情况；matrix = [["1"]]，期望输出1，验证单元素；matrix = [["1","0","1","0","0"]]，只有一行时，期望输出1，因为连续的1区间最多只有一个；matrix = [["1","1","1","1"]]，期望输出4，验证一行内连续1全取的情况。
我建议提交前把这几组用例都跑一遍，尤其是全0矩阵，很多人因为循环里 heights 更新逻辑写错，在这里栽跟头。
5. 相似题目与举一反三
5.1 每日一题周边：84、221 与热榜100题
LeetCode 85题不是孤立的，它和好几道热门题构成一条知识链。先说84题"柱状图中最大的矩形"，那是85题的一维底座。务必先把84题独立刷懂，能把单调栈的思路从头到尾讲清楚，再回来做85题。
然后是221题"最大正方形"，它和85题共享"二维矩阵里找全1区域"的设定。区别在于，221题限定了形状必须是正方形，所以可以用动态规划，状态转移方程dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，简洁漂亮。而85题不限形状，矩形的高宽可以自由伸缩，反而不能直接用同样的DP，只能回到单调栈。这两个题目并排刷，能帮你理解“限制条件如何影响算法选型”。
除此之外，热榜100题里还有不少单调栈的变体，比如接雨水（42题）、每日温度（739题）、下一个更大元素（496题）。这些题的核心都是“找某个元素左边或右边第一个比它大/小的位置”，和85题弹栈时确定左右边界是同一个套路。我建议把这几题放在一块集中刷，三天之内突破单调栈这个技术点。
5.2 面试中的延伸考法
面试官在85题基础上最常见的延伸是：不要求返回面积，而是要求返回矩形左上角和右下角的坐标，或者要求把最大矩形标记出来。这种时候你需要在计算面积的同时记录最优矩形的位置信息。
具体做法也不难：在单调栈弹栈计算面积时，除了算面积，还要记录对应的高度值和左右边界，然后比较面积大小，更新最佳矩形坐标。左边界是栈空时的0或者弹出后新栈顶的下一个位置，右边界是当前扫描位置减1。最终得到最优高度 h、左边界 l、右边界 r，再结合当前底边所在行数，就能还原整个矩形区域。
另一种问法是要求输出最大矩形区域内的所有坐标，那更简单，拿到矩形的高和宽之后，从底边向上扩展即可。
还有一种考法是把二维矩阵换成字符矩阵，比如char[][]，逻辑一样，但字符比较时注意类型。更有意思的是，有些面试官会给你一个标注了权重的矩阵，每个1带一个数值，要求最大化权重之和而不是面积，这个就变成贪心或DP问题了，已经超出了85题的范围，但它的出发点仍然是从这个题目展开的。
5.3 周赛与每日一题刷题思路
最近 LeetCode 每日一题也经常出一些硬核题目。如果你平时在追每日一题，会发现单调栈类题型的出现频率相当高。周赛430里虽然没有直接考85题，但有一道题也需要用“维护一个前缀数组配合单调栈”的思路。这种“热门题+变体”的联动正是刷题的正确姿势：把一道题的解法内化成工具，遇到新题时先想想能不能套工具，再想工具怎么改。
就我个人经验来说，每日一题的价值不在于每天多刷一道题，而在于题型之间的联系。你今天刷的85题，可能正是下周某道周赛题的思路跳板。所以每次刷完一道题，花十分钟想一想“这题跟哪个经典题是同家族”，收获远大于多刷十道新题。
6. 我的实操体会与建议
前面写了不少干货，最后聊一点个人经验。
我第一次做85题的时候，其实84题已经刷过了，但还是卡了很久。原因很搞笑：我一直在纠结“怎么在二维矩阵上直接跑单调栈”，想找到一个抽象的二维单调结构，结果越钻越深，完全忘了“逐行转化为一维柱状图”这个最基本的思路。后来在草稿纸上画了几行高度数组，才意识到自己想复杂了。从那以后我就养成了一个习惯：遇到二维问题，先试着把它压缩成一维问题再思考。这个“降维思考”的思路，后来在处理很多矩阵类题目时都帮了大忙。
实操中还有一个小技巧值得分享：如果时间紧张，不用每次都把85题的完整代码默写出来，但一定要能在纸上画出“某一行高度数组 + 单调栈弹栈过程”的两步演示图。面试时把这个图画出来，把“每一行底边、向上连续1的数量、左右边界”这几个概念串起来，基本就能证明你是真的理解了，而不是背了答案。
另外，LeetCode 的代码编辑器支持直接运行测试用例，建议把评论区里别人贴的稀奇古怪的矩阵也复制过来跑一下。矩阵类问题的坑往往藏在形状不对称、边界行、全0列这些刁钻用例里，多跑几个变态用例，比反复提交十次都更能增加信心。
最后，如果矩阵特别大，比如 1000×1000 的规模，单调栈版本在 Python 里也可能接近时间上限。这时候可以考虑两种优化：一是把 heights 的更新和单调栈计算合并到同一个循环里，减少函数调用开销；二是将 matrix 的每一行转成字节数组再用 numpy 操作更新列累加，但这种写法放在面试里反而显得不自然，实战刷题一般没必要用。
这题刷透之后，建议马上去刷221题最大正方形，再回来把84题的题解重新看一遍。三题联动吃下来，单调栈和二维矩阵问题这个分支基本就算打通了。后续遇到任何“找最大 XXX 形状区域”的题，你的第一反应都会是：能不能先降维，能不能用单调栈。这种条件反射，就是刷题最实在的收获。
