题目链接
难度：困难 类型：动态规划
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例
输入:
[["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
输出: 6
解题思路
矩形的面积等于，分别找出
和
即可
- 计算
row[i]是matrix的第i行，每行有n列，例如示例中，n=5
到达第行时
当row[i][j] == '0' 时(其中)，
当row[i][j] == '1' 时(其中
例如，i = 2时，h = [3, 1, 3, 2, 2]，每一行都要求出h，一共求4组 - 找到
对于第2行的h，[3, 1, 3, 2, 2]，前三行所构成的矩形的面积可以是1，2，3，4，6，这是因为去了不同的所造成的
当是，面积等于6
[["x","x","x","x","x"],
["x","x","1","1","1"],
["x","x","1","1","1"],
["x","x","x","x","x"]
当是，面积等于5
[["x","x","x","x","x"],
["x","x","x","x","x"],
["1","1","1","1","1"],
["x","x","x","x","x"]
找出所有的的组合，像极了84题：柱状图中最大的矩形
代码实现
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
height = [0] * (n+1)
max_area = 0
for row in matrix:
# 计算h
for i in range(n):
height[i] = height[i]+1 if row[i]=='1' else 0
# 找出所有h和w的组合
stack = [-1]
for j in range(n + 1):
while height[j] < height[stack[-1]]:
h = height[stack.pop()]
w = j - 1 - stack[-1]
max_area = max(max_area, h * w)
stack.append(j)
return max_area
