企业官网建设流程全解析

LeetCode 85. 最大矩形 —— 学习笔记

题目

给定一个只包含'0'和'1'的二维矩阵，找出只包含'1'的最大矩形，返回其面积。

一、整体思路（骨架）

核心策略：把二维问题拆成一维问题，逐行处理。

1. 矩阵变柱状图：把矩阵的每一行都当作"地面"，往上数每一列连续1的个数，这个数字就是这一列"柱子"的高度。这样矩阵的每一行都能对应出一组柱状图。
2. 柱状图求最大矩形：对每一行生成的柱状图，用单调栈求出这组柱子里能围成的最大矩形面积。
3. 取所有行的最大值：把每一行算出来的最大面积做比较，取全局最大值，就是整个矩阵的答案。

举例验证（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,n=len(matrix),len(matrix[0])# pre[j]：从当前行往上数，第j列连续'1'的高度# 多开一位(n+1)作为"结尾哨兵"，高度恒为0，保证每行最后能把栈清空结算pre=[0]*(n+1)res=0foriinrange(m):# 第一部分：更新这一行的柱子高度forjinrange(n):pre[j]=pre[j]+1ifmatrix[i][j]=="1"else0# 第二部分：单调栈求这一排柱子的最大矩形stack=[-1]# -1是"起始哨兵"，代表最左边界之外，避免栈空时取stack[-1]报错fork,numinenumerate(pre):whilestack[-1]!=-1andpre[stack[-1]]>num:index=stack.pop()height=pre[index]width=k-stack[-1]-1res=max(res,height*width)stack.append(k)returnres

四、我出现过的问题清单

五、我提出过的疑问及解答要点

1. pre为什么要开n+1长度？
   末尾多出的哨兵（高度恒为0）保证每行扫描结束时，栈里剩余的柱子都会被强制触发弹出结算，避免漏算。

2. stack为什么初始要放一个-1？
   避免栈被弹空后再取stack[-1]导致报错（IndexError），同时让"左边界=最左端"这种情况可以用统一公式k-stack[-1]-1处理，不用额外写if判断。

3. while stack[-1]!=-1 and pre[stack[-1]]>num中，一开始stack[-1]不就是-1吗，条件不是执行不了？
   while嵌套在外层for k循环里，每次外层循环都会重新检查一次这个条件。第一次检查时确实栈顶是-1，条件不成立、跳过；但紧接着会执行stack.append(k)，把栈顶变成真实下标，下一次外层循环再检查时，栈顶已经不是-1了，条件才有可能成立。