• 分类：HashTable/DP

• 考察知识点：HashTable DP(动态规划) Stack

• 最优解时间复杂度：*O(mn) **

85. Maximal Rectangle

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

代码：

DP解法:

class Solution:
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res=0
        
        m=len(matrix)
        if m==0:
            return res
        n=len(matrix[0])
        if n==0:
            return res

        height=[0]*n
        left=[0]*n
        right=[n]*n

        for i in range(m):

            curLeft=0
            curRight=n

            for j in range(n):
                # 每次循环设定height
                if matrix[i][j]=="1":
                    height[j]+=1
                else:
                    height[j]=0

                # 每次循环设定left
                if matrix[i][j]=="1":
                    #虽然我现在也不知道这里为啥要max(curLeft,left[j])
                    left[j]=max(curLeft,left[j])
                else:
                    left[j]=0
                    curLeft=j+1

                # 每次循环设定right
                if matrix[i][n-j-1]=="1":
                    right[n-j-1]=min(right[n-j-1],curRight)
                else:
                    right[n-j-1]=n
                    curRight=n-j-1

            for j in range(n):
                res=max(res,(height[j]*(right[j]-left[j])))

        return res

Stack解法:

class Solution:
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        res=0

        m=len(matrix)
        if m==0:
            return res
        n=len(matrix[0])
        if n==0:
            return res

        #前面是有数的，最后一个height为0
        height=[0]*(n+1)

        for i in range(m):

            stack_list=[]

            for j in range(n+1):
                if j<n:
                    # 每次循环设定height
                    if matrix[i][j]=="1":
                        height[j]+=1
                    else:
                        height[j]=0

                if (len(stack_list)==0) or (height[j]>=height[stack_list[len(stack_list)-1]]):
                    stack_list.append(j)
                else:
                    while (len(stack_list)!=0 and height[j]<height[stack_list[len(stack_list)-1]]):
                        h=height[stack_list.pop()]
                        width=0
                        if len(stack_list)==0:
                            width=j
                        else:
                            width=j-stack_list[len(stack_list)-1]-1
                        res=max(res,h*width)
                    stack_list.append(j)

        return res

讨论：

1.这个题是一道特别难的题，第一种DP的想法是非常难想到的，也非常的巧妙。第二种解法是来自于84的题的升级，更加通用一些
2.这个题目挺重要的，在公式面试中出现的频率中等
3.stack中的这个width是一个基底的概念，港真挺难的- -
4.所以stack中存的是什么？如果height[i]>=height[stack[-1]],也就说如果height较大的就存在里头，height*有height的底座
5.不要看CSinpriation他的讲解- -有错误的

DP.jpeg

Stack.jpeg