作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址: https://leetcode.com/problems/maximal-rectangle/description/
题目描述：
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
题目大意
给出了一个二维的数组，求在这里面能够成的最大的矩形面积是多少。
解题方法
本以为会和221. Maximal Square做法一样使用DP解决，可是感觉状态转移方程太复杂，所以还是参考了84. Largest Rectangle in Histogram升级版的解法。
如图所示，如果把每一行的1和它上面的1连在一起，那么就可以看成一个个站里的矩形方块。那么我们的最终目的就是找出最大面积的矩形方块，所以就是第84题的做法了，使用单调栈。
需要注意的是，我们使用一个height数组，保存到某一层的第i个位置为止，能向上构成的矩形的高度。而且需要对每层都做一个寻找面积的操作，最终选择所有层中能够成矩形面积最大值。
时间复杂度是O(M(N+M))，空间复杂度是O(N)。
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 日 —— 冻成狗