leetcode 85 最大矩形 矩阵
按照矩阵行，每一行为基准线，将矩阵中1的数字看作条形统计图中的柱体，计算最大的矩形。每一行迭代。
利用前缀和思想，当当前元素为1，则加上之前的元素，当为0,则清零。
计算的柱体面积按照之前最大矩形面积的题目，构造递增单调栈，但遇到比栈顶元素低的元素，就可以计算以栈顶元素高度的面积。
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if len(matrix)==0:
return 0
result=0
height=[0 for i in range(len(matrix[0]))]
def find_max(height):
stack=[]
height=height+[0]
maxvalue=0
for i in range(len(height)):
while stack and height[stack[-1]]>=height[i]:
s=stack[-1]
stack=stack[:-1]
if not stack:
sidx=-1
else:
sidx=stack[-1]
maxvalue=max(maxvalue,(i-sidx-1)*height[s])
stack.append(i)
print(maxvalue)
return maxvalue
for i in range(len(matrix)):
#print(matrix[i])
for j in range(len(matrix[i])):
if matrix[i][j]=="1":
height[j]+=1
else:
height[j]=0
result=max(result,find_max(height))
return result
暴力的方法，先计算每行连续1的个数，即为宽度，然后以这个宽度从当前行向上搜索，找出宽度最小的值，即为当前高度（i-k+1)的对应宽度，这样遍历看什么时候矩形面积会达到最大。其中遍历连续1数值宽度的时候，需要在前一个值上面加1，也就是在前一个宽度的值上面加1。
同时由于时间的限制，当上面宽度有一个是0时，即剪枝，break。
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
height=[[0 for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
maxvalue=0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]=='1':
if j>=1:
height[i][j]=height[i][j-1]+1
else:
height[i][j]=1
else:
height[i][j]=0
width=height[i][j]
print(width)
for k in range(i,-1,-1):
if height[k][j]==0:
break
width=min(width,height[k][j])
maxvalue=max(maxvalue,width*(i-k+1))
return maxvalue通过记录每一个节点左右第一个小于该节点值的位置，来计算以当前节点值为高的矩形面积，每次需要将左右数组分别初始化-1，和len(matrix[0])
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if len(matrix)==0:
return 0
height=[0 for _ in range(len(matrix[0]))]
maxvalue=0
for i in range(len(matrix)):
#height=[0 for _ in range(len(matrix[0]))]
for j in range(len(matrix[0])):
if matrix[i][j]=='1':
height[j]+=1
else:
height[j]=0
print(height)
left=[-1 for _ in range(len(matrix[0]))]
right=[len(matrix[0]) for _ in range(len(matrix[0]))]
for j in range(len(matrix[0])):
for t in range(0,j):
if height[t]<height[j]:
left[j]=max(t,left[j])
for j in range(len(matrix[0])):
for t in range(j+1,len(matrix[0])):
if height[t]<height[j]:
right[j]=min(t,right[j])
print(left)
print(right)
for j in range(len(matrix[0])):
print(maxvalue)
maxvalue=max(maxvalue,(right[j]-left[j]-1)*height[j])
return maxvalue动态规划，初始化一个三维数组，一维记录该节点向左的连续的节点数，二维记录向上的节点数，三维记录目前的最大矩形数值。每次当遍历到数组为1的时候再去更改记录的数值，当i==0 和 j==0时说明无法向上和向左，那么更新左和上的值都为1，如果是i==0,那么应该更新左的值，在左面前一个值的基础上加1，j==0,更新上的值，在上面前一个值的基础上加1，当都不为0时，左面和上面的值都在前一个值的基础上加1，然后根据上面值，去遍历哪一个左面的值最小来计算当前高度的矩形值。这样不断的寻找最大的值。
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
dp=[[[0 for _ in range(3)] for _ in range(len(matrix[0]))]for _ in range(len(matrix))]
maxvalue=0
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j]=="1":
if i==0 and j==0:
dp[i][j][0]=1
dp[i][j][1]=1
dp[i][j][2]=1
elif i==0:
dp[i][j][0]=1#向上
dp[i][j][1]=dp[i][j-1][1]+1
dp[i][j][2]=dp[i][j-1][2]+1
elif j==0:
dp[i][j][1]=1#向左
dp[i][j][0]=dp[i-1][j][0]+1
dp[i][j][2]=dp[i-1][j][2]+1
else:
dp[i][j][0]=dp[i-1][j][0]+1
dp[i][j][1]=dp[i][j-1][1]+1
height=dp[i][j][1]
col=dp[i][j][0]#向上
print(col)
for t in range(col):
height=min(dp[i-t][j][1],height)
dp[i][j][2]=max(dp[i][j][2],height*(t+1))
#print(dp)
maxvalue=max(maxvalue,dp[i][j][2])
return maxvalue
飞鱼科技公司福利 126人发布
