poj2559 Largest Rectangle in a Histogram

洛谷上做过一道一样的题(P1719 最大加权矩形)，但是没写博客...

现在已一个新高度来看待这题，沿用以前的方法，感觉很好(草稿纸模拟数小时后20分钟AC)

就是对于每一个位置，记录能够往右延伸多远。

然后反着做一遍，记录能向左多远。

单调栈算法。

当然也有扫一遍即可的算法，但是写着烦，就没写。

 #include <cstdio>

 using namespace std;

 const int N = ;

 typedef long long LL;

 LL Q[N], t, h[N], l[N];

 inline void max(LL &a, const LL b) {

     if(a < b) a = b;

     return;

 }

 int main() {

     int n;

     while(scanf("%d", &n)) {

         if(n == ) {

             break;

         }

         t = ;

         for(int i = ; i <= n; i++) {

             scanf("%lld", &h[i]);

         }

         h[n + ] = ;

         for(int i = ; i <= n + ; i++) {

             Q[++t] = i;

             while(h[Q[t - ]] > h[i]) {

                 l[Q[t - ]] = i - Q[t - ] - ;

                 Q[t - ] = Q[t--];

             }

         }

         t = ;

         for(int i = n; i >= ; i--) {

             Q[++t] = i;

             while(h[Q[t - ]] > h[i]) {

                 l[Q[t - ]] += (Q[t - ] - i);

                 Q[t - ] = Q[t--];

             }

         }

         long long ans = ;

         for(int i = ; i <= n; i++) {

             max(ans, h[i] * l[i]);

         }

         printf("%lld\n", ans);

     }

     return ;

 }

AC代码

巴特西

poj2559 Largest Rectangle in a Histogram

最新文章

热门文章