LeetCode 85. 最大矩形 —— 学习笔记题目给定一个只包含0和1的二维矩阵找出只包含1的最大矩形返回其面积。一、整体思路骨架核心策略把二维问题拆成一维问题逐行处理。矩阵变柱状图把矩阵的每一行都当作地面往上数每一列连续1的个数这个数字就是这一列柱子的高度。这样矩阵的每一行都能对应出一组柱状图。柱状图求最大矩形对每一行生成的柱状图用单调栈求出这组柱子里能围成的最大矩形面积。取所有行的最大值把每一行算出来的最大面积做比较取全局最大值就是整个矩阵的答案。举例验证3行4列矩阵行0: 1 0 1 1 行1: 1 0 1 1 行2: 1 1 1 1走到行2时柱子高度是[3,1,3,3]其中列2、列3高度都是3能围成 3行×2列6 的矩形对应原矩阵中真实存在的一块全1区域。二、柱状图求最大矩形单调栈是怎么工作的朴素思路没有栈的版本对每根柱子往左找第一个比它矮的柱子左边界往右找第一个比它矮的柱子右边界宽度 右边界 - 左边界 - 1面积 宽度 × 自身高度。所有柱子里取最大值。问题如果对每根柱子都单独扫一遍去找左右边界时间复杂度是 O(n²)太慢。单调栈怎么优化成 O(n)栈里存的是下标且栈内下标对应的高度从栈底到栈顶保持递增或相等。右边界从左往右扫描时第一次遇到比栈顶矮的柱子那个位置就是栈顶柱子的右边界——不用额外找扫描过程中顺路就发现了。左边界某根柱子被弹出时栈里剩下的新栈顶就是它的左边界。原因能留在栈里的柱子一定是从它自己到当前位置之间从未被更矮的柱子打败过所以新栈顶到当前位置之间的柱子必然都 ≥ 被弹出柱子的高度。记忆口诀栈顶柱子被弹出的那一刻弹它的那个新柱子是它的右边界弹出后剩下的新栈顶是它的左边界。等高柱子的处理连续几根一样高的柱子会依次被弹出每次都各自算一次面积。中间几次算出来的面积可能偏小但其中总有一次通常是这一串里最左边那根被弹出时会用到真正最远的左边界算出最大的那个矩形所以不影响最终取max的结果。三、完整代码含详细注释fromtypingimportListclassSolution:defmaximalRectangle(self,matrix:List[List[str]])-int:ifnotmatrixornotmatrix[0]:# 空矩阵直接返回0return0m,nlen(matrix),len(matrix[0])# pre[j]从当前行往上数第j列连续1的高度# 多开一位(n1)作为结尾哨兵高度恒为0保证每行最后能把栈清空结算pre[0]*(n1)res0foriinrange(m):# 第一部分更新这一行的柱子高度forjinrange(n):pre[j]pre[j]1ifmatrix[i][j]1else0# 第二部分单调栈求这一排柱子的最大矩形stack[-1]# -1是起始哨兵代表最左边界之外避免栈空时取stack[-1]报错fork,numinenumerate(pre):whilestack[-1]!-1andpre[stack[-1]]num:indexstack.pop()heightpre[index]widthk-stack[-1]-1resmax(res,height*width)stack.append(k)returnres四、我出现过的问题清单问题原因修正if matrix is None: return None没考虑matrix[]这种空矩阵形式且返回值应该是面积数字不是None改成if not matrix or not matrix[0]: return 0matrix[i][j]1判断恒为False矩阵里存的是字符串1不是整数1改成matrix[i][j]1while stack[-1]!-1 and stack[-1]num拿下标直接和高度比较维度不对改成pre[stack[-1]]num先用下标查出真实高度再比较五、我提出过的疑问及解答要点pre为什么要开n1长度末尾多出的哨兵高度恒为0保证每行扫描结束时栈里剩余的柱子都会被强制触发弹出结算避免漏算。stack为什么初始要放一个-1避免栈被弹空后再取stack[-1]导致报错IndexError同时让左边界最左端这种情况可以用统一公式k-stack[-1]-1处理不用额外写if判断。while stack[-1]!-1 and pre[stack[-1]]num中一开始stack[-1]不就是-1吗条件不是执行不了while嵌套在外层for k循环里每次外层循环都会重新检查一次这个条件。第一次检查时确实栈顶是-1条件不成立、跳过但紧接着会执行stack.append(k)把栈顶变成真实下标下一次外层循环再检查时栈顶已经不是-1了条件才有可能成立。