分类：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
