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