Given a rows x cols binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Example 1:
Input: matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]] Output: 6 Explanation: The maximal rectangle is shown in the above picture.
- code
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix:
return 0
def calRecHistogram(height):
stack = [-1]
maxArea = 0
for i in range(len(height)):
while stack[-1] != -1 and height[i] <= height[stack[-1]]:
curHeight = height[stack.pop()]
curWidth = i - 1 - stack[-1]
maxArea = max(maxArea, curHeight * curWidth)
stack.append(i)
while stack[-1] != -1:
curHeight = height[stack.pop()]
curWidth = len(height) - 1 - stack[-1]
maxArea = max(maxArea, curHeight * curWidth)
return maxArea
res = 0
height = [0] * len(matrix[0])
for row in range(len(matrix)):
for col in range(len(matrix[0])):
if matrix[row][col] == "0":
height[col] = 0
else:
height[col] += 1
res = max(res, calRecHistogram(height))
return res