# 最大矩形
给定一个仅包含 0
和 1
、大小为 rows x cols
的二维二进制矩阵,找出只包含 1
的最大矩形,并返回其面积。
示例 1:
输入:matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出:6
解释:最大矩形如上图所示。
示例 2:
输入:matrix = []
输出:0
示例 3:
输入:matrix = [["0"]]
输出:0
示例 4:
输入:matrix = [["1"]]
输出:1
示例 5:
输入:matrix = [["0","0"]]
输出:0
提示:
rows == matrix.length
cols == matrix[0].length
0 <= row, cols <= 200
matrix[i][j]
为 '0'
或 '1'
以下程序实现了这一功能,请你填补空白处内容:
```python
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if matrix is None or len(matrix) == 0:
return 0
ls_row, ls_col = len(matrix), len(matrix[0])
left, right, height = [0] * ls_col, [ls_col] * ls_col, [0] * ls_col
maxA = 0
for i in range(ls_row):
curr_left, curr_right = 0, ls_col
for j in range(ls_col):
if matrix[i][j] == '1':
height[j] += 1
else:
height[j] = 0
for j in range(ls_col):
if matrix[i][j] == '1':
left[j] = max(left[j], curr_left)
else:
left[j], curr_left = 0, j + 1
_______________________
for j in range(ls_col):
maxA = max(maxA, (right[j] - left[j]) * height[j])
return maxA
# %%
s = Solution()
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
print(s.maximalRectangle(matrix))
```
## template
```python
class Solution(object):
def maximalRectangle(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if matrix is None or len(matrix) == 0:
return 0
ls_row, ls_col = len(matrix), len(matrix[0])
left, right, height = [0] * ls_col, [ls_col] * ls_col, [0] * ls_col
maxA = 0
for i in range(ls_row):
curr_left, curr_right = 0, ls_col
for j in range(ls_col):
if matrix[i][j] == '1':
height[j] += 1
else:
height[j] = 0
for j in range(ls_col):
if matrix[i][j] == '1':
left[j] = max(left[j], curr_left)
else:
left[j], curr_left = 0, j + 1
for j in range(ls_col - 1, -1, -1):
if matrix[i][j] == '1':
right[j] = min(right[j], curr_right)
else:
right[j], curr_right = ls_col, j
for j in range(ls_col):
maxA = max(maxA, (right[j] - left[j]) * height[j])
return maxA
# %%
s = Solution()
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
print(s.maximalRectangle(matrix))
```
## 答案
```python
for j in range(ls_col - 1, -1, -1):
if matrix[i][j] == '1':
right[j] = min(right[j], curr_right)
else:
right[j], curr_right = ls_col, j
```
## 选项
### A
```python
for j in range(ls_col - 1, -1, -1):
if matrix[i][j] == '1':
right[j], curr_right = ls_col, j
else:
right[j] = min(right[j], curr_right)
```
### B
```python
for j in range(ls_col - 1, -1, -1):
if matrix[i][j] == '1':
right[j], curr_right = ls_col, j
else:
right[j] = max(right[j], curr_right)
```
### C
```python
for j in range(ls_col - 1, -1, -1):
if matrix[i][j] == '1':
right[j] = max(right[j], curr_right)
else:
right[j], curr_right = ls_col, j
```