# 最大矩形

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

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

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
static inline int max(int a, int b)
{
	return a > b ? a : b;
}
static int area_calc(int *heights, int size)
{
	int *indexes = malloc(size * sizeof(int));
	int *lhist = malloc(size * sizeof(int));
	int *rhist = malloc(size * sizeof(int));
	int i, pos = 0;
	for (i = 0; i < size; i++)
	{
		while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
		{
			pos--;
		}
		lhist[i] = pos == 0 ? -1 : indexes[pos - 1];
		indexes[pos++] = i;
	}
	pos = 0;
	for (i = size - 1; i >= 0; i--)
	{
		_________________________;
	}
	int max_area = 0;
	for (i = 0; i < size; i++)
	{
		int area = heights[i] * (rhist[i] - lhist[i] - 1);
		max_area = max(area, max_area);
	}
	return max_area;
}
static int maximalRectangle(char **matrix, int matrixRowSize, int matrixColSize)
{
	int i, j, max_area = 0;
	int *heights = malloc(matrixColSize * sizeof(int));
	memset(heights, 0, matrixColSize * sizeof(int));
	for (i = 0; i < matrixRowSize; i++)
	{
		for (j = 0; j < matrixColSize; j++)
		{
			heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
		}
		max_area = max(max_area, area_calc(heights, matrixColSize));
	}
	return max_area;
}
int main(int argc, char **argv)
{
	if (argc < 2)
	{
		fprintf(stderr, "Usage: ./test row1 row2...\n");
		exit(-1);
	}
	int i, j;
	int row_size = argc - 1;
	int col_size = strlen(argv[1]);
	for (i = 0; i < row_size; i++)
	{
		printf("%s\n", argv[i + 1]);
	}
	printf("%d\n", maximalRectangle(argv + 1, argc - 1, strlen(argv[1])));
	return 0;
}
```

## template

```cpp
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
static inline int max(int a, int b)
{
	return a > b ? a : b;
}
static int area_calc(int *heights, int size)
{
	int *indexes = malloc(size * sizeof(int));
	int *lhist = malloc(size * sizeof(int));
	int *rhist = malloc(size * sizeof(int));
	int i, pos = 0;
	for (i = 0; i < size; i++)
	{
		while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
		{
			pos--;
		}
		lhist[i] = pos == 0 ? -1 : indexes[pos - 1];
		indexes[pos++] = i;
	}
	pos = 0;
	for (i = size - 1; i >= 0; i--)
	{
		while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
		{
			pos--;
		}
		rhist[i] = pos == 0 ? size : indexes[pos - 1];
		indexes[pos++] = i;
	}
	int max_area = 0;
	for (i = 0; i < size; i++)
	{
		int area = heights[i] * (rhist[i] - lhist[i] - 1);
		max_area = max(area, max_area);
	}
	return max_area;
}
static int maximalRectangle(char **matrix, int matrixRowSize, int matrixColSize)
{
	int i, j, max_area = 0;
	int *heights = malloc(matrixColSize * sizeof(int));
	memset(heights, 0, matrixColSize * sizeof(int));
	for (i = 0; i < matrixRowSize; i++)
	{
		for (j = 0; j < matrixColSize; j++)
		{
			heights[j] = matrix[i][j] == '1' ? heights[j] + 1 : 0;
		}
		max_area = max(max_area, area_calc(heights, matrixColSize));
	}
	return max_area;
}
int main(int argc, char **argv)
{
	if (argc < 2)
	{
		fprintf(stderr, "Usage: ./test row1 row2...\n");
		exit(-1);
	}
	int i, j;
	int row_size = argc - 1;
	int col_size = strlen(argv[1]);
	for (i = 0; i < row_size; i++)
	{
		printf("%s\n", argv[i + 1]);
	}
	printf("%d\n", maximalRectangle(argv + 1, argc - 1, strlen(argv[1])));
	return 0;
}
```

## 答案

```cpp
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
	pos--;
}
rhist[i] = pos == 0 ? size : indexes[pos - 1];
indexes[pos++] = i;
```

## 选项

### A

```cpp
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
	pos--;
}
rhist[i] = pos == 0 ? indexes[pos - 1] : size;
indexes[pos++] = i;
```

### B

```cpp
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
	pos--;
}
rhist[i] = pos == 0 ? size : indexes[pos + 1];
indexes[pos++] = i;
```

### C

```cpp
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
	pos++;
}
rhist[i] = pos == 0 ? size : indexes[pos - 1];
indexes[pos++] = i;
```