原题
给你一个二维矩阵，权值为False和True，找到一个最大的矩形，使得里面的值全部为True，输出它的面积
样例
给你一个矩阵如下
[
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 1],
[0, 0, 1, 1, 1],
[0, 0, 0, 0, 1]
]
输出6
解题思路
转化
- 根据上图，可以清楚的看出本题可以转化为Largest Rectangle in Histogarm来做
- 初始化height = [0, 0 ,0 ....]
- 对于每一行，先求出以这一行为x轴的每个柱子的高度，求解时，可以每次基于上一行的值进行更新。然后O(n)的时间求出最大矩形，不断更新全局变量res
- 时间复杂度为 O(n * (n + n)) = O(n2)
完整代码
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
res = 0
if not matrix:
return res
height = [0 for i in range(len(matrix[0]))]
for row in matrix:
for i in range(len(row)):
if row[i] == '0':
height[i] = 0
else:
height[i] += 1
res = max(res, self.largestRectangleArea(height))
return res
def largestRectangleArea(self, height):
if not height:
return 0
res = 0
stack = []
height.append(-1)
for i in range(len(height)):
current = height[i]
while len(stack) != 0 and current <= height[stack[-1]]:
h = height[stack.pop()]
w = i if len(stack) == 0 else i - stack[-1] - 1
res = max(res, h * w)
stack.append(i)
return res
