题目描述：

给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积。

上图是每条宽度为1, 高度 =[2,1,5,6,2,3]的直方图。

图中的阴影部分是该直方图中面积最大的矩形，面积为10个单位。 例如： 给出的高度 =[2,1,5,6,2,3], 返回10.

输入描述：

第一行输入一个整数n，表示边长数目。
第二行输入n个边长，以空格分隔。

输出描述：

输出一个整数，表示最大矩形面积。

示例输入：

6
2 1 5 6 2 3

示例输出：

10

题解：

#include<stdio.h>
int main(void){
	int n;
	scanf("%d",&n);
	int arr[n];
	int max_area=0; //最大面积 
	int i,j;
	for(i=0;i<n;i++){//输入边长 
		scanf("%d",&arr[i]);
	}
	//定义栈(动态规划)
	int stack[n];
	int top=-1;//-1代表栈空
	int temp; //保存边长 
	int area; //保存面积 
	for(i=0;i<n;i++){
		if(top==-1 || arr[stack[top]]<=arr[i]){ //栈为空或者Hi<Hi+1 
			stack[++top]=i; 
		}else{//若不递增 
			temp=stack[top--];//取出最大边长下标 
			area=arr[temp]*(top==-1?i:i-stack[top]-1);//计算面积 
			if(area>max_area){
				max_area=area; 
			}
			i--;
		} 
	}
	//栈不为空时
	while(top!=-1){
		temp=stack[top--];//取出最大边长下标 
			area=arr[temp]*(top==-1?i:i-stack[top]-1);//计算面积 
			if(area>max_area){
				max_area=area; 
			}
	}
	printf("%d",max_area);
	return 0;
}