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

题目来源：

庞果网

题目简介：

给定直方图，每一小块的height由N个非负整数所确定，每一小块的width都为1，请找出直方图中面积最大的矩形。    如下图所示，直方图中每一块的宽度都是1，每一块给定的高度分别是[2,1,5,6,2,3]：    那么上述直方图中，面积最大的矩形便是下图所示的阴影部分的面积，面积= 10单位。    请完成函数largestRectangleArea，实现寻找直方图中面积最大的矩形的功能，如当给定直方图各小块的高度= [2,1,5,6,2,3] ，返回10。

代码（本代码在anycodex在线编程网站上测试通过，Try yourself?）：

#include <stdio.h>

int largestRectangleArea(const int *height,int n) {
    int i = 0;
    int j = 0;
    int count = 1;
    int maxResult = 0;
    int temp;
    for (; i < n; i++)
    {
        count = 1;
        if ( i == 0)       // only check the right one if it is the first element
        {
            if ( *(height + i + 1) >= *(height + i))     //if the right element is bigger or equal than the one
            {
                for ( j = i + 1; j < n; j++)      //then calculate from the right
                {
                    if (*(height + j) >= *(height + i))
                        count++;
                    else
                        break;
                }
            }
            temp = count * *(height + i);
            maxResult = temp > maxResult ? temp: maxResult;
            continue;
        }
        else if ( i == n -1 )                    //only check the left side if it is the last element
        {
            if ( *(height + i - 1) >= *(height + i))     //if the left element is bigger or equal than the one
            {
                for ( j = i - 1; j >= 0; j--)      //then calculate from the left
                {
                    if (*(height + j) >= *(height + i))
                        count++;
                    else
                        break;
                }
            }
            temp = count * *(height + i);
            maxResult = temp > maxResult ? temp: maxResult;
            break;
        }
        else
        {
            if (*(height + i + 1) >= *(height + i) && *(height + i -1) < *(height + i))     //a[i+1] >= a[i] but a[i-1] < a[i]
            {
                for ( j = i + 1; j < n; j++)      //then calculate from the right
                {
                    if (*(height + j) >= *(height + i))
                        count++;
                    else
                        break;
                }
                temp = count * *(height + i);
                maxResult = temp > maxResult ? temp: maxResult;
            }
            else if (*(height + i + 1) < *(height + i) && *(height + i -1) >= *(height + i))     //a[i+1] < a[i] but a[i-1] >= a[i]
            {
                for ( j = i - 1; j >= 0; j--)      //then calculate from the left
                {
                    if (*(height + j) >= *(height + i))
                        count++;
                    else
                        break;
                }
            }
            else if (*(height + i + 1) >= *(height + i) && *(height + i -1) >= *(height + i))     //a[i+1] >= a[i] but a[i-1] >= a[i]
            {
                //printf("a[i] a[i+1] a[i-1] %d %d %dn", *(p + i), *(p + i + 1), *(p + i -1));
                for ( j = i - 1; j >= 0; j--)      //firstly, calculate from the left
                {
                    if (*(height + j) >= *(height + i))
                        count++;
                    else
                        break;
                }
                for ( j = i + 1; j < n; j++)      //then calculate from the right
                {
                    if (*(height + j) >= *(height + i))
                        count++;
                    else
                        break;
                }
            }
            temp = count * *(height + i);
            maxResult = temp > maxResult ? temp: maxResult;
        }
        //printf("The maxResult in each round is %dn", maxResult);
    }
    return maxResult;  
}



//start 提示：自动阅卷起始唯一标识，请勿删除或增加。
int main()
{    
    //
    int a[] = {2,1,5,6,3,1};
    int len = sizeof(a)/sizeof(int);
    int result;
    result = largestRectangleArea((const int *)a,len);
    printf("The largest rectangle area is %dn", result);
    return 0;
}

欢迎关注新浪微博： ThreadX

共同学习，共同进步，菜鸟求组队。

最后

以上就是想人陪睫毛为你收集整理的寻找直方图中面积最大的矩形的全部内容，希望文章能够帮你解决寻找直方图中面积最大的矩形所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。