# 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
以下程序实现了这一功能，请你填补空白处的内容：
```cpp
#include
#include
static int largestRectangleArea(int *heights, int heightsSize)
{
int *indexes = malloc(heightsSize * sizeof(int));
int *left = malloc(heightsSize * sizeof(int));
int *right = malloc(heightsSize * sizeof(int));
int i, pos = 0;
for (i = 0; i < heightsSize; i++)
{
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
pos--;
}
left[i] = pos == 0 ? -1 : indexes[pos - 1];
indexes[pos++] = i;
}
pos = 0;
for (i = heightsSize - 1; i >= 0; i--)
{
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
pos--;
}
right[i] = pos == 0 ? heightsSize : indexes[pos - 1];
indexes[pos++] = i;
}
int max_area = 0;
_______________________
return max_area;
}
int main(void)
{
int nums[] = {2, 1, 5, 6, 2, 3};
int count = sizeof(nums) / sizeof(*nums);
printf("%d\n", largestRectangleArea(nums, count));
return 0;
}
```
## template
```cpp
#include
#include
static int largestRectangleArea(int *heights, int heightsSize)
{
int *indexes = malloc(heightsSize * sizeof(int));
int *left = malloc(heightsSize * sizeof(int));
int *right = malloc(heightsSize * sizeof(int));
int i, pos = 0;
for (i = 0; i < heightsSize; i++)
{
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
pos--;
}
left[i] = pos == 0 ? -1 : indexes[pos - 1];
indexes[pos++] = i;
}
pos = 0;
for (i = heightsSize - 1; i >= 0; i--)
{
while (pos > 0 && heights[indexes[pos - 1]] >= heights[i])
{
pos--;
}
right[i] = pos == 0 ? heightsSize : indexes[pos - 1];
indexes[pos++] = i;
}
int max_area = 0;
for (i = 0; i < heightsSize; i++)
{
int area = heights[i] * (right[i] - left[i] - 1);
max_area = area > max_area ? area : max_area;
}
return max_area;
}
int main(void)
{
int nums[] = {2, 1, 5, 6, 2, 3};
int count = sizeof(nums) / sizeof(*nums);
printf("%d\n", largestRectangleArea(nums, count));
return 0;
}
```
## 答案
```cpp
for (i = 0; i < heightsSize; i++)
{
int area = heights[i] * (right[i] - left[i] - 1);
max_area = area > max_area ? area : max_area;
}
```
## 选项
### A
```cpp
for (i = 0; i < heightsSize; i++)
{
int area = heights[i] * (right[i] - left[i] - 1);
max_area = area > max_area ? max_area : area;
}
```
### B
```cpp
for (i = 0; i < heightsSize; i++)
{
int area = heights[i] * (right[i] - left[i]);
max_area = area > max_area ? max_area : area;
}
```
### C
```cpp
for (i = 0; i < heightsSize; i++)
{
int area = heights[i] * (right[i] - left[i]);
max_area = area > max_area ? area : max_area;
}
```