class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if len(matrix) == 0:
return 0
# 在这里被 wa 一次
n, m =
len(matrix), len(matrix[0])
mt = map(
lambda x: map(int, x), matrix)
height, maxArea = [0
for i
in range(0, m+1
)], 0
stack =
[]
for i
in range(0, n):
for j
in range(1, m+1
):
height[j] = (height[j] + 1) * mt[i][j-1
]
level, tmp = 1
, 0
stack = [(1
,m)]
while True:
if len(stack) ==
0:
break
tstack =
[]
for (wi, wj)
in stack:
for j
in range(wi, wj+1
):
if height[j] >=
level:
tmp += 1
else:
if tmp >
0:
tstack.append((j-tmp, j-1
))
maxArea = max(maxArea, tmp*
level)
tmp =
0
if tmp >
0: # 这里能不能不这么做？代码重复啊
tstack.append((wj-tmp+1
, wj))
maxArea = max(maxArea, tmp*
level)
tmp =
0
stack =
tstack
level += 1
return maxArea
if __name__ ==
'__main__':
a =
Solution()
print a.maximalRectangle([[
"1",
"0",
"1",
"0",
"0"],[
"1",
"0",
"1",
"1",
"1"],[
"1",
"1",
"1",
"1",
"1"],[
"1",
"0",
"0",
"1",
"0"]])
一开始准备用二维 DP 来做，但是发现不好写。看了别人用了 height 数组解决此题，后面写了上述题解。
转载于:https://www.cnblogs.com/tmortred/p/8042753.html
