leetcode 85.最大矩形(python)
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
动态规划
class Solution(object):
def maximalRectangle(self
, matrix
):
if not matrix
or not matrix
[0]:
return 0
n
= len(matrix
[0])
height
= [0] * (n
+ 1)
ans
= 0
for row
in matrix
:
for i
in range(n
):
height
[i
] = height
[i
] + 1 if row
[i
] == '1' else 0
stack
= [-1]
for i
in range(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
