# 最大矩形

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

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

```java
class Solution {
	public int maximalRectangle(char[][] matrix) {
		if (matrix == null || matrix.length == 0)
			return 0;
		int m = matrix.length;
		int n = matrix[0].length;
		int[] left = new int[n];
		int[] right = new int[n];
		int[] height = new int[n];
		Arrays.fill(right, n);
		int cur_left = 0;
		int cur_right = n;
		int res = 0;
		for (int i = 0; i < m; i++) {
			cur_left = 0;
			cur_right = n;
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1')
					height[j]++;
				else
					height[j] = 0;
			}
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1') {
					left[j] = Math.max(left[j], cur_left);
				} else {
					left[j] = 0;
					cur_left = j + 1;
				}
			}
			for (int j = n - 1; j >= 0; j--) {
				if (matrix[i][j] == '1') {
					right[j] = Math.min(right[j], cur_right);
				} else {
					right[j] = n;
					cur_right = j;
				}
			}
			______________________;
		}
		return res;
	}
}

```

## template

```java
class Solution {
	public int maximalRectangle(char[][] matrix) {
		if (matrix == null || matrix.length == 0)
			return 0;
		int m = matrix.length;
		int n = matrix[0].length;
		int[] left = new int[n];
		int[] right = new int[n];
		int[] height = new int[n];
		Arrays.fill(right, n);
		int cur_left = 0;
		int cur_right = n;
		int res = 0;
		for (int i = 0; i < m; i++) {
			cur_left = 0;
			cur_right = n;
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1')
					height[j]++;
				else
					height[j] = 0;
			}
			for (int j = 0; j < n; j++) {
				if (matrix[i][j] == '1') {
					left[j] = Math.max(left[j], cur_left);
				} else {
					left[j] = 0;
					cur_left = j + 1;
				}
			}
			for (int j = n - 1; j >= 0; j--) {
				if (matrix[i][j] == '1') {
					right[j] = Math.min(right[j], cur_right);
				} else {
					right[j] = n;
					cur_right = j;
				}
			}
			for (int j = 0; j < n; j++)
				res = Math.max(res, (right[j] - left[j]) * height[j]);
		}
		return res;
	}
}

```

## 答案

```java
for (int j = 0; j < n; j++)
	res = Math.max(res, (right[j] - left[j]) * height[j]);
```

## 选项

### A

```java
for (int j = 0; j < n; j++)
	res = Math.max(res, (right[j] + left[j]) * height[j]);
```

### B

```java
for (int j = 0; j < n; j++)
	res = Math.max(res, (right[j] + left[j]) / 2 * height[j]);
```

### C

```java
for (int j = 0; j < n; j++)
	res = Math.max(res, (right[j] - left[j]) / 2 * height[j]);
```