# 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
``````

## # 解题方法

``````class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]: return 0
M, N = len(matrix), len(matrix[0])
height = [0] * N
res = 0
for row in matrix:
for i in range(N):
if row[i] == '0':
height[i] = 0
else:
height[i] += 1
res = max(res, self.maxRectangleArea(height))
return res

def maxRectangleArea(self, height):
if not height: return 0
res = 0
stack = list()
height.append(0)
for i in range(len(height)):
cur = height[i]
while stack and cur < height[stack[-1]]:
w = height[stack.pop()]
h = i if not stack else i - stack[-1] - 1
res = max(res, w * h)
stack.append(i)
return res
``````

https://www.jianshu.com/p/cffdc94c9c19

## # 日期

2018 年 10 月 10 日 —— 冻成狗