LeetCode 85
Borrow the idea from Largest Rectangle in Histogram, we can take the matrix as many histograms for each row level, in which we scan from top to down cumulatively to construct it:
| Matrix | Histograms |
|---|
| 1 |
1 |
0 |
0 |
| 1 |
0 |
1 |
0 |
| 0 |
1 |
1 |
0 |
| 0 |
1 |
1 |
1 |
| 1 |
1 |
1 |
1 |
|
| 1 |
1 |
0 |
0 |
| 2 |
0 |
1 |
0 |
| 0 |
1 |
2 |
0 |
| 0 |
2 |
3 |
1 |
| 1 |
3 |
4 |
2 |
|
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
|
class Solution:
def largestRectangleArea(self, heights):
stack, max_area = [], 0
heights.append(0)
for i in range(len(heights)):
while stack and heights[i] < heights[stack[-1]]:
popped_idx = stack.pop()
height = heights[popped_idx]
left = stack[-1] + 1 if stack else 0
right = max(i-1, 0)
width = right - left + 1
max_area = max(max_area, height*width)
stack.append(i)
return max_area
def maximalRectangle(self, matrix: List[List[str]]) -> int:
n_row, n_col = len(matrix), len(matrix[0])
max_area = 0
heights = [0]*n_col
for i in range(n_row):
for j in range(n_col):
if matrix[i][j] == "1":
heights[j] += 1
else:
heights[j] = 0
max_area = max(max_area, self.largestRectangleArea(heights))
return max_area
|
Notes
- Actually this is not a dp solution