Hdu 1506 Largest Rectangle in a Histogram

佚名 5年前 (2019-07-25) 算法 1669人围观抢沙发百度已收录

原题链接：Largest Rectangle in a Histogram

题意简析：

　　首先我们得对我们的问题进行一个总结：给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。这样抽象出来之后，很显然我们可以用单调栈解决此题。

　　我们建一个栈，用来保存若干矩形，这些矩形的高度是单调递增的，我们从左到右依次扫描每个矩形：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　　　如果当前矩形比栈顶矩形高，直接进栈。

　　　　否则不断取出栈顶，直至栈为空，或者栈顶矩形的高度比当前矩形小。在出栈过程中，我们累计被弹出的矩形的宽度之和，并且每弹出一个矩形，就用它的高度乘上累计的宽度去更新答案。整个出栈过程结束后，我们把一个高度为当前矩形的高度、宽度为累计值的新矩形入栈。

　　　　整个扫描结束后，我们把栈中剩余的矩形依次弹出，按照上面的相同的方法更新答案。为了简化程序实现，也可以增加一个高度为0的矩形a[n + 1]，以避免在扫描结束后栈中有剩余。

代码如下：

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 100010;
int n, top;
ll ans;
int s[N], w[N], a[N];
int main(){
    
    while(scanf("%d", &n) && n){
        ans = 0;
        for(int i = 1; i <= n; i++)        scanf("%d", &a[i]);
        a[n + 1] = top = 0;
        for(int i = 1; i <= n + 1; i++){
            if( a[i] > s[top]){
                s[++top] = a[i], w[top] = 1;
            }
            else{
                int width = 0;
                while(s[top] > a[i]){
                    width += w[top];
                    ans = max(ans, (ll)width * s[top]);
                    --top;
                }
                s[++top] = a[i];    w[top] = width + 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}