题意：

求出最大的可以用矩形覆盖的面积

思路：

这题和[USACO 2009 Mar S]Look Up类似，我们只要找到每个矩形左边第一个比它矮的地方和右边第一个比它矮的地方，然后 这两个距离之差 * 矩形高 就行了，从左往右走，如果遇到一个比之前遇到的最高的矮，那就说明那个最高的矩形的面积最大也只能到这了，算出面积后这个矩形就可以不要了。也就是说存的时候是有个单调性的，从矮到高，而且一次操作只对当前最高的矩形进行处理，就能用个栈来存储。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
int a[N];
#define PII pair<int,int>//分别存长度和高度
#define ll long long
#define x first
#define y second
int main(){
    
    while(1)
    {
        int n,x;
        cin>>n;
        if(n==0)break;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        stack<PII> st;
        ll ans=0;
        for(int i=1;i<=n;i++)
        {
            int pos=i;
            while(!st.empty() && a[i]<=st.top().x)//如果是一样高的话，要加进来的矩形肯定在那个一样高的矩形右边，也就是比之前那个宽，所以直接删掉之前的，加上现在的。
            {
                pos=min(pos,st.top().y);//pos是这个要加进来的矩形最左能到的位置，因为要删除的矩形比它高，所以加进来的矩形左端点就可以扩展到要删除的矩形的左端点
                ans=max(ans,(ll)(i-pos)*st.top().x);
                st.pop();
            }
            st.push({a[i],pos});
        }
        while(!st.empty()) //从进来到结束都没有遇到比自己矮的或者等高的
        {
            ans=max(ans,(ll)(n-st.top().y+1)*st.top().x);
            st.pop();
        }
        cout<<ans<<endl;
        
        
        
        
    }
    
    
    return 0;
}