继续看挑战赛的算法，虽然不指望能得到什么奖项，但能够将自己的思想用程序表达出来就是一种乐趣！

请看题：

我的解题思路：

就是判断[i,i+1,i+2...j]之间的最小高度H，然后通过s=(j-i+1)*H来计算面积，然后筛选出最大的面积。

C++代码：

//寻找直方图中面积最大的矩形 #include <cstdio> #include <cstring> #include <string> #include <vector> #include <stack> #include <iostream> using namespace std;   //返回一段区间中最矮的那个索引 int short(vector<int> arr,int start,int end)   {     int short=arr[start];   int index=start;   int i;   if(start==end)   {   return index;    }       for(i=start;i<=end;i++)   {      if(short>=arr[i])   {   short=arr[i];   index=i;   }   }   return index;   }   int largestRectangleArea(vector<int> &height) { int area = 0; int max = 0; int height_index=0; for (int i=0;i<height.size();i++) { for (int j=i;j<height.size();j++) { height_index=shortest(height,i,j);   area=(j-i+1)*(height[height_index]);   if(max < area)   max=area;   } } return max; }

关于C++泛型的一些东西，可以去看我博客中的这部分内容：http://blog.csdn.net/dingxiaowei2013/article/details/9814495

C++具有模板还稍微好一点，如果用C写可以用指针来写

C语言代码：

#include <stdio.h>  //找出区间最小值的索引 int shortindex(const int * height,int begin,int end) { 	int shortindex; 	int shortheight=*height; 	if (begin=end) 	{ 		return begin; 	} 	else 	{ 		for (int i=begin;i<end;i++,height++) 		{ 			if (shortheight>*height) 			{ 				shortheight=*height; 				shortindex=i; 			} 		} 		return shortindex; 	} 	 }  //数组指针，数组个数 int largestRectangleArea(const int *height,int n) { 	int area = 0; 	int max = 0; 	int height_index = 0; 	for (int i=0;i<n;i++) 	{ 		for (int j=i;j<n;j++) 		{ 			height_index=shortindex(height,i,j); 			area = (j-i+1)*(height[height_index]); 			if (max<area) 			{ 				max=area; 			} 		} 	} 	return max; }

==================== 迂者 丁小未 CSDN博客专栏=================

MyBlog：http://blog.csdn.net/dingxiaowei2013             MyQQ:1213250243

Unity QQ群：858550         cocos2dx QQ群：280818155

====================== 相互学习，共同进步 ===================

转载请注明出处：http://blog.csdn.net/dingxiaowei2013/article/details/17472397

欢迎关注我的微博：http://weibo.com/u/2590571922

本文转蓬莱仙羽51CTO博客，原文链接：http://blog.51cto.com/dingxiaowei/1366175，如需转载请自行联系原作者