【题目描述】： 地面上从左到右并排紧挨着摆放多个矩形，已知这此矩形的底边宽度都为1，高度不完全相等。求在这些矩形包括的范围内能得到的面积最大的矩形，打印出该面积。所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。 如 n = 7, 序列为2 1 4 5 1 3 3 _ _ _ | | _ | | | || | _ _ |H||H| _ _ _ | || | | || | _ |H||H| | || | | | _ | || | _ | || | | | _ |H||H| _ | || | |_||_||_||_||_||_||_| |_||_||H||H||_||_||_| 最大面积：8

【输入描述】： 输入有多组数据，每组数据一行： 第一个数N，表示矩形个数 后面跟N个正整数，第i个正整数hi表示第i个矩形的高度。 最后一行，以一个单独的0结束。

【输出描述】： 每组输入数据一行，一个数表示最大矩形面积。

【样例输入】： 7 2 1 4 5 1 3 3 4 1000 1000 1000 1000 0

【样例输出】： 8 4000

【时间限制、数据范围及描述】： 时间：1s 空间：64M 30 %: 1<=N<=100 60 %: 1<=N<=1,000 100%: 1<=N<=500,000，0<=hi<=1,000,000,000

单调栈版子题

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;const int N=1000005;long long n,h[N],q[N],p[N],i,ans,top=1,tmp,now;long long max(long long x,long long y){ return x>y?x:y;}int main(){ while(scanf("%lld",&n)){ if(!n){ break; } memset(h,0,sizeof(h)); memset(q,0,sizeof(q)); memset(p,0,sizeof(p)); top=1; ans=0; for(i=1;i<=n;i++){ scanf("%lld",&h[i]); } n+=1; for(i=1;i<=n;i++){ now=i; while(h[i]
            
             q[top-1]){ q[top]=h[i]; p[top]=now; top++; } } printf("%lld\n",ans); } return 0;}