寻找直方图中面积最大的矩形

nemon

寻找直方图中面积最大的矩形题目详情:

给定直方图，每一小块的height由N个非负整数所确定，每一小块的width都为1，请找出直方图中面积最大的矩形。

   如下图所示，直方图中每一块的宽度都是1，每一块给定的高度分别是[2,1,5,6,2,3]：

   那么上述直方图中，面积最大的矩形便是下图所示的阴影部分的面积，面积= 10单位。

   请完成函数largestRectangleArea，实现寻找直方图中面积最大的矩形的功能，如当给定直方图各小块的高度= [2,1,5,6,2,3] ，返回10。

1. int largestRectangleArea(const int *height,int n) {
   
2.     int max=0,i,p,h,j;
   
3.     for(i=0;i<n;i++)
   
4.     {
   
5.         h=*(height+i);
   
6.         p=i-1;
   
7.         j=1;
   
8.         while(p>=0 && *(height+p)>=h){j++;p--;}
   
9.         p=i+1;
   
10.         while(p<n && *(height+p)>=h){j++;p++;}
    
11.         if((j*h)>max)max=j*h;
    
12.     }
    
13.     return max;
    
14. }

复制代码

油炸冰激凌

哈哈，第一眼看题还没看懂