-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path085 Maximal Rectangle.py
33 lines (30 loc) · 1.15 KB
/
085 Maximal Rectangle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
'''
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
'''
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0 for __ in range(n + 1)]
result = 0
for row in matrix:
for i in range(n):
heights[i] = heights[i] + 1 if row[i] == '1' else 0
stack = [-1]
for i in range(n + 1):
while heights[i] < heights[stack[-1]]:
h = heights[stack.pop()]
w = i - stack[-1] - 1
result = max(result, h * w)
stack.append(i)
return result
if __name__ == "__main__":
assert Solution().maximalRectangle([['1', '1', '0', '1', '0', '1'],
['0', '1', '0', '0', '1', '1'],
['1', '1', '1', '1', '0', '1'],
['1', '1', '1', '1', '0', '1']]) == 8