本文共 977 字，大约阅读时间需要 3 分钟。

题意：7 2 1 4 5 1 3 3  直接讲数据 ：给出7个矩形的高，底长都为1，求最大的连通的矩形块的面积

思路：如果暴力的话肯定超时，有一个特别巧妙的预处理，如果我们知道每一个矩形的左右两边能延伸到哪就好了，这相当于一个并查集：如果我找到了 i ，并且小于等于第 i-1 的高度，那 i-1 的左边界就赋给 i ,向递归一样找下去，直到最左边或者 i 的高度小于左边界的左边。右边界也是这样。

注意：特别注意一下代码中数组的初始化还有最后边界相减加一.

#include
   
    long long f[100010],l[100010],r[100010],n;int main(){    while(~scanf("%lld",&n)&&n)    {        for(int i=1;i<=n;i++)            scanf("%lld",&f[i]);        for(int i=1;i<=n;i++)            l[i]=r[i]=i;//i点的左右边界初始化为本身        f[0]=-1,f[n+1]=-1;//端点初始化        //相当于并查集        for(int i=1;i<=n;i++)        {            while(f[i]<=f[l[i]-1])//f[i]与当前边界的前面的点比较 若小于等于                l[i]=l[l[i]-1];//f[i]的左边界l[i]为前面的点的边界  直到小于f[i]为止        }        for(int i=n;i>=1;i--)        {            while(f[i]<=f[r[i]+1])//f[i]与f[i]当前边界的后一个数比较 若小于等于                r[i]=r[r[i]+1];//前面的数的右边界r[r[i]-1]更新最右边界        }        long long sum=0,ans=0;        for(int i=1;i<=n;i++)        {            sum=(r[i]-l[i]+1)*f[i];//边界相减加 1            if(ans
   

转载地址：http://ygsl.baihongyu.com/