# 85. Maximal Rectangle¶

## Information¶

• Diffculty: Hard

• Created: 2020-03-10 09:29:00

• Last Motified: 2020-03-10 09:51:40

• Tags: Array, Hash Table, Dynamic Programming, Stack

## Intuition¶

We could handle it by rows.

In each row, it is easily to get the maximum height of the current column by DP. Because dp[i][j] = dp[i - 1][j] + 1 if matrix[i][j] is 1, else it is 0.

With this dp array, we could use the algorithm we used in problem <85. Largest Rectangle in Histogram> to get the maximum area of the rectangle ends with each node.

## Solution¶

```class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]:
return 0
m, n = len(matrix), len(matrix[0])
dp = [0] * (n + 1)
max_area = 0
for i in range(m):
# Use DP to get the height of each column
for j in range(n):
if matrix[i][j] == "1":
dp[j] += 1
else:
dp[j] = 0

# Use stack to get the maximum area
stack = [[-1, -1]]
for index, height in enumerate(dp):
i = index
while stack[-1][0] >= height:
h, i = stack.pop()
area = h * (index - i)
max_area = max(area, max_area)
stack.append([height, i])
return max_area
```