跟编程挑战赛干上了系列之容错处理的重要性

题目详情

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

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

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

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

由于受到了CSDN上一篇介绍推特面试题的想法很容易找到了一个比较好的算法，且算法的复杂度为O（N)。

大概想法是这样的，要找到最大面积的矩形，首先要找到以每一个小块为起点（起点这个词可能不太准确，可继续往后看）对应的最大矩形面积，然后在这些候选最大矩形面积中找出最大值，即为所求直方图中的面积最大矩形。

第一步：如何找出以每一个小块为起点对应的最大矩形面积？

以题目所给的用例为例来说明。

如第一个小块的高度为2，第二个小块的高度为1，第二个小块高度小于第一个小块，所以第一个小块对应的最大矩形面积为2X1=2.

如第二个小块的高度为1，第一个小块的高度为2大于第二个小块，第三、四、五、六个小块的高度也均大于第二个小块，所以第二个小块对应的最大矩形面积为1X6=6。

接下来介绍一下计算每个小块对应最大矩形面积的算法，这就是我借鉴那道推特面试题的地方。

首先按顺序从第一个小块开始从左至右前向遍历一遍数组，以第二个小块为例，每遇到右边小块高度大于它的高度时，其对应宽度加1。遇到高度比其低时，停止。

接着按顺序以最后一个小块开始从右至左后向遍历一遍数组，以第二个小块为例，每遇到左边小块高度大于它的高度时，其对应宽度加1。遇到高度比其低时，停止。

最后，依次将每个小块的高度和其宽度相乘，得到其对应的最大矩形面积。

第二步：就是在上面得到的候选最大矩形面积中找出最大的面积，作为函数的返回值就OK了。

下面是自己写的代码，虽然不够简洁，但是还是能够正常运行滴。

#include <stdio.h>

int largestRectangleArea(const int *height,int n) {
    int i,j;//定义两个循环变量
    int N=n;//这步多余了，完全没必要
    int temp;//零时中间变量
    int max1,max2;
    int* a=malloc(n*sizeof(int));//动态分配一个数组，用来存放每个小块对应的宽度
    for(i=0;i<N;i++)
     {
        *(a+i)=*(height+i);
     }
     for(i=0;i<N-1;i++)
     {
         if(*(a+i)>*(a+i+1))
         {
         temp=*(a+i+1);
         *(a+i+1)=*(a+i);
         *(a+i)=temp;
         }
      }
      max1=*(a+N-1);
      printf("%d\n",max1);
    for(i=0;i<N;i++)
    {
        *(a+i)=0;
    }
    for(i=0;i<N;i++)
    {
        j=i;
        while(((*(height+i))<=(*(height+j)))&&(j<N))
        {
            (*(a+i))+=(*(height+i));
            j++;
        }
     }
     
     for(i=0;i<N;i++)
     {
         
         printf("%d   ",*(height+i));
     }
      for(i=N-1;i>0;i--)
    {
        j=i;
        while(((*(height+i))<=(*(height+j-1)))&&(j>=0))
        {
            *(a+i)+=*(height+i);
            j--;
        }
     }
     printf("\n");
     for(i=0;i<N;i++)
     {
         printf("%d   ",*(a+i));
         
     }
     
     for(i=0;i<N-1;i++)
     {
         if(*(a+i)>*(a+i+1))
         {
         temp=*(a+i+1);
         *(a+i+1)=*(a+i);
         *(a+i)=temp;
         }
      }
     
     max2=*(a+n-1);
     free(a);
     printf("\n%d",max2);
     return (max2>max1)?max2:max1;     
    }





//start 提示：自动阅卷起始唯一标识，请勿删除或增加。
int main()
{    
    //
    int height[11]={100,6,6,6,6,3,6,6,6,6,6};
    printf("\n%d\n",largestRectangleArea(height,11));
    return 0;
}
//end //提示：自动阅卷结束唯一标识，请勿删除或增加。

本以为已经可以拿到了十分的，结果坑在后面，而且掉进去了很久才知道是这个坑。

提交代码后提示执行用户样例失败，为什么呢？

首先我想到了是非负整数，我定义的是变量int型，可能计算出现问题，我换成unsigned int型依然没起来；

其次我想到了是计算溢出，于是我把int型改为long long int 够长吧，结果还是长跪不起。

最后的最后我又想了很多很多，包括是不是算法出问题了，我把我能想到的所有用例都试了一遍，长跪不起。

泼出去了，去网上搜了一下别人怎么解决的，其中有一个人的算法和我用的一样，链接为http://blog.csdn.net/SunnyYoona/article/details/16931047

最核心的区别就是在这

if(height == NULL || n <= 0){
return 0;
}

加上这个坑爹的容错处理，提交本人的代码就成功了，只可惜来的太迟，10分飞了。

亲，写程序一定要记得考虑容错处理额。

秒客网

跟编程挑战赛干上了系列之容错处理的重要性

相关文章