Week5 作业 A

题目描述：

给一个直方图，求直方图中的最大矩形的面积。例如，下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1，其中最大的矩形是阴影部分

 思路：

对于第i个矩形，以其高度h[i]能组成的最大矩形是通过如下方式求的：找出i左边第一个高度小于h[i]的，和i右边第一个高度大于h[i]的，用长度乘以h[i]就是了。对于每一个矩形进行这样的操作，找出其中的最大值就行了。

找的过程可以用单调栈来解决，这里以找右边界R[i]为例：从1到n进行遍历，维护一个单调栈（从栈底到栈顶递增），当进入的元素a[i]大于等于栈顶元素时，进栈，否则弹出栈顶元素x，同时说明x的最右边界就是i-1，然后继续判断栈顶元素，直到栈顶元素小于等于a[i]，然后把i进栈，继续向后搜索；

所有元素都搜索完毕后，可能有一部分的R[i]==0，说明这些元素的右边界没确定，也就是说，从i到n一直在递增；这些元素一定都还在栈中，处理一下即可。

找出每个i的左右边界之后，取 h[i]*(R[i]-L[i]) 的最大值即可。

代码：

#include <cstdio>
#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN=1e5+5;
typedef long long ll;
stack<int> S;
ll a[MAXN],ans;
int R[MAXN],L[MAXN];  //R[i]=k表示a[i]右边的边界是k,其元素是a[k] 
int main()
{
    int n;
    while( scanf("%d",&n) && n!=0 )
    {
        memset( a,0,sizeof(a) );
        memset( R,0,sizeof(R) );
        memset( L,0,sizeof(L) );
        ans=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",a+i);
            while( !S.empty() && a[ S.top() ]>a[i] )
            {
                R[ S.top() ] =i-1;             //如果遇到连续递增的,则其R[i]=0;否则一定R[i]!=0; 
                S.pop();
            }
            S.push(i);
        }
        while( !S.empty() )    //如果栈中还有元素则说明其R[i]=0;
        {
            R[ S.top() ]=n;
            S.pop();
        } 
        for(int i=n;i>=1;i--)
        {
            while( !S.empty() && a[ S.top() ]>a[i] )
            {
                L[ S.top() ] =i+1;             //如果遇到连续递增的,则其L[i]=0;否则一定L[i]!=0; 
                S.pop();
            }
            S.push( i );     
        }
        while( !S.empty() )    //如果栈中还有元素则说明其L[i]=0;
        {
            L[ S.top() ]=1;
            S.pop();
        } 
        for(int i=1;i<=n;i++)
        {
            ll tmp=a[i]*(R[i]-L[i]+1);
            ans=max( ans,tmp );
        }
        cout<<ans<<endl;
    }
    return 0;
}