UESTC_秋实大哥去打工 2015 UESTC Training for Data Structures

G - 秋实大哥去打工

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit Status

天行健，君子以自强不息。地势坤，君子以厚德载物。

天天过节的秋实大哥又要过节了，于是他要给心爱的妹子买礼物。但由于最近秋实大哥手头拮据，身为一个男人，他决定去打工！

秋实大哥来到一家广告公司。现在有n块矩形墙从左至右紧密排列，每一块高为Hi，宽为Wi。

公司要求秋实大哥找出一块最大的连续矩形区域，使得公司可以在上面贴出最大的海报。

Input

第一行包含一个整数n，表示矩形墙的个数。

接下来n行，每行有两个整数Wi，Hi，表示第i块墙的宽度和高度。

1≤n≤200000，保证Wi，Hi以及最后的答案<231。

Output

最大的连续矩形的面积。

Sample input and output

Sample Input	Sample Output
3 3 4 1 2 3 4	14

解题报告

关键是找到某个元素所能扩展到的最远位置，我们维护一个单调栈即可，扫描一遍，若该元素大于栈顶元素则入栈，若小于则出栈并更新答案，注意可能一直单调递增，可在最后加一个高度为0的虚矩形，保证扫描结束后所有合法矩形已经全部出栈.

 #include <iostream>
 #include <algorithm>
 #include <cstring>
 #include <cstdio>
 typedef long long ll;
 using namespace std;
 const int maxn = 2e5 + ;
 int h[maxn],w[maxn],sum[maxn],s[maxn],pos[maxn];

 int main(int argc,char *argv[])
 {
   int n;
   scanf("%d",&n);
   for(int i =  ; i <= n ; ++ i)
    scanf("%d%d",&w[i],&h[i]);
   sum[] = ;
   h[n+] = ;
   for(int i =  ; i <= n ; ++ i)
    sum[i] = sum[i-] + w[i];
   int top =  , ans =  ;
   for(int i =  ; i <= n+ ; ++ i)
    {
          if (top >  && h[i] < s[top-])
           {
                 while(top >  && h[i] < s[top-])
                  ans = max(ans , (sum[i-] - sum[pos[--top]-])*s[top]);
           s[top++] = h[i];
        }
       else
        {
              pos[top] = i;
              s[top++] = h[i];
        }
    }
   printf("%d\n",ans);
   return ;
 }