题目链接本题目是84题的升级版。84题可以暴力暴力解决（但是84题不能用类似的策略解决）=0:return0m=len(matrix[0])max_l=[[0]*mforiinrange(n)]foriinrange(n):cur=0forjinrange(m):如果matrix[i][j]=='1':cur+=1else:cur=0max_l[i][j]=curans=0foriinrange(n):forjinrange(m):ifmatrix[i][j]=='1':minl=max_l[i][j]forkinrange(i,n):ifmatrix[k][j]=='0':breakminl=min(minl,max_l[k][j])ans=max(ans,minl*(k-i+1))返回ansmax_l是每个点向左延伸多少格。计算max_l矩阵遍历n×m。然后从每一个点开始，把这个点看成是右上顶点的矩形的最大面积，需要沿着n方向遍历。所以时间复杂度为O(n^2×m)转化为多个84题，上面的方法max_l对每一行使用增量堆栈方法的每一列相当于一个84题。下面的代码直接从问题84中获取代码并为每一行调用该函数。类解决方案：deflargestRectangleArea(self,heights:List[int])->int:hs=[0]+heights+[0]s=[]ans=0fori,hinenumerate(hs):whilesandhs[s[-1]]>h:j=s.pop()ans=max(ans,hs[j]*(i-s[-1]-1))s.append(i)返回ansdefmaximalRectangle(self,matrix:List[List[str]])->int:n=len(matrix)如果n==0:return0m=len(matrix[0])dp=[int(i)foriinmatrix[0]]ans=self.largestRectangleArea(dp)foriinrange(1,n):forjinrange(m):ifmatrix[i][j]=='1':dp[j]+=1else:dp[j]=0ans=max(ans,self.largestRectangleArea(dp))returnansdynamicprogramming从1的每个位置我们可以计算出这样一个矩形在当前位置的面积：高度应该尽可能的高扩展（到上面的第一个0或者边界）尽可能的宽，那么全局最大的区域一定在里面。任何点都有一个h高度，l左边界，r右边界。矩形的面积是h×(r-l)其中l是点左边第一个0（或边界）右边的元素的下标。r是最右边的0或（边界）索引。这里h很容易计算。当前为0，h设置为0。如果不为0，则h为上一行的h加1。l和r，以l为例，始终保持当前左边界，（初始为0）如果当前为1，l为当前左边界与上一行左边界的最大值（因为我们要查看整个左边界的情况）；如果当前为0，则更新当前左边界为当前下标加一，并将l设为0。（这里设0并不是一开始真的是0，对这条线的位置计算不起作用（因为当前位置h必须为0，一次乘法为0）主要相当于重置状态，下一行左边的边界不受这行限制，r的情况类似。类解决方案：defmaximalRectangle(self,matrix:List[List[str]])->int:n=len(matrix)ifn==0:return0m=len(matrix[0])l=[0]*mr=[m]*mh=[0]*mans=0foriinrange(n):forjinrange(m):ifmatrix[i][j]=='1':h[j]+=1else:h[j]=0cur=0forjinrange(m):ifmatrix[i][j]=='1':l[j]=max(cur,l[j])else:cur=j+1l[j]=0cur=mforjinrange(m-1,-1,-1):ifmatrix[i][j]=='1':r[j]=min(cur,r[j])else:r[j]=mcur=jforjinrange(m):ans=max(ans,h[j]*(r[j]-l[j]))returnans欢迎来我的博客：https://codeplot.top/我博客问题分类：https://codeplot.top/categories/%E5%88%B7%E9%A2%98/
