主要思想来自
http://blog.csdn.net/wuyanyi/article/details/7243580
题目的连接，头次提交的同学需要注册
http://acm.nyist.net/JudgeOnline/problem.php?pid=258
此题多年前出现在江湖之中，微软面试100题有，2014网易有道又冲出江湖，此题是单调栈的使用，想了两天，明白一点。得不断的思考啊
其实还是从最简单的（n2）优化而来。总的思路是：
1。每个矩形只出栈一次，入站一次。
2.出栈的时候表明该矩形不能往右边扩展了，所以可以出栈，同时在该矩形入站的时候我们已经计算了它右边的扩展的寛。
总而言之：入站记录了向右扩展
出栈记录了向左扩展
这个思路比较好理解，但是提交之后效率，确实低，但是很容易扩展到不同的，其实数组不用定义，直接输入就行，浪费了，其次是了long long 改为 int型，知识点有漏洞，就是计算机的不骂表示应该掌握，还有就是 Int float表示范围等，高精度，大数据值得联系。
#include<iostream>
#include<stack>
using namespace std; struct node
{
long long h;
long long w; }n[100006];
int main()
{
int len;
while(cin>>len&&len)
{
long long max=-1;//所求的答案
for(int i=0;i<len;i++)
{
cin>>n[i].h;
n[i].w=1;
}
stack<node> s; s.push(n[0]);
for(int i=1;i<len;i++)
{
if(n[i].h>=s.top().h) //如果当前节点的高大于栈顶，则加入
{ s.push(n[i]); }
else
{
long long sumw=0;
while(!s.empty()&&s.top().h>=n[i].h)
{ node n2=s.top();
s.pop();
sumw=sumw+n2.w ;
long long temp=sumw*n2.h;
if(temp>max)
{
max=temp;
} } n[i].w+=sumw;
s.push(n[i]); } } long long sumw=0;
while(!s.empty())
{
node n2=s.top();
s.pop();
sumw+=n2.w;
if(sumw*n2.h>max)
{
max=sumw*n2.h;
} } cout<<max<<endl; } return 0;
system("pause");
}