# 最大矩形

<p>给定一个仅包含 <code>0</code> 和 <code>1</code> 、大小为 <code>rows x cols</code> 的二维二进制矩阵，找出只包含 <code>1</code> 的最大矩形，并返回其面积。</p><p> </p><p><strong>示例 1：</strong></p><img alt="" src="https://img-service.csdnimg.cn/img_convert/52f17607758af8beae7a87191bff1795.jpeg" style="width: 402px; height: 322px;" /><pre><strong>输入：</strong>matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]<strong><br />输出：</strong>6<strong><br />解释：</strong>最大矩形如上图所示。</pre><p><strong>示例 2：</strong></p><pre><strong>输入：</strong>matrix = []<strong><br />输出：</strong>0</pre><p><strong>示例 3：</strong></p><pre><strong>输入：</strong>matrix = [["0"]]<strong><br />输出：</strong>0</pre><p><strong>示例 4：</strong></p><pre><strong>输入：</strong>matrix = [["1"]]<strong><br />输出：</strong>1</pre><p><strong>示例 5：</strong></p><pre><strong>输入：</strong>matrix = [["0","0"]]<strong><br />输出：</strong>0</pre><p> </p><p><strong>提示：</strong></p><ul>	<li><code>rows == matrix.length</code></li>	<li><code>cols == matrix[0].length</code></li>	<li><code>0 <= row, cols <= 200</code></li>	<li><code>matrix[i][j]</code> 为 <code>'0'</code> 或 <code>'1'</code></li></ul>

以下程序实现了这一功能，请你填补空白处内容：

```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
```