hard目前一共110题左右，6.21到今天终于刷到了第20题。
85. Maximal Rectangle
这题没做出来，不仅没做出来，连思路都没有
如果类比于上一题，就是loop每一行，然后把每一行当成底边，然后计算当前行为底边的时候，可以形成的最大矩阵
这题简直了，不知道有没有其它方法可以解决
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
height = [0] * (n + 1)
ans = 0
for row in matrix:
# 对于当前行，利用上一行的height来计算当前行的最大矩形
# 如果类比于上一题，就是loop每一行，然后把每一行当成底边，然后计算当前行为底边的时候，可以形成的最大矩阵
for i in xrange(n):
height[i] = height[i] + 1 if row[i] == '1' else 0
stack = [-1]
for i in xrange(n + 1):
while height[i] < height[stack[-1]]:
h = height[stack.pop()]
w = i - 1 - stack[-1]
ans = max(ans, h * w)
stack.append(i)
return ans
