有一天，LC给我们出了一道题，如图：

这个图形从左到右由若干个 宽为1 高不确定 的小矩形构成，求出这个图形所包含的最大矩形面积。

思路:开两个数组分别记录每一个矩形以他为中心所能达到的左右长度,然后面积就是h*（r-l+1）；这里要注意的是如果该矩形比上一个或后一个矩形要小,则上一个矩形所能达到的区间,该矩形一定可以达到,
ac代码：
#include<stdio.h>
int main()
{   int a[101];
    int n,max,i;
    while(scanf("%d",&n)!=EOF)
    {   
      if(n==0)
        break;
    for(i=1;i<=n;i++)
       scanf("%d",&a[i]);
    int l[101],r[101];
    l[1]=1;
    r[n]=n;
    int t;
    for(i=2;i<=n;i++)
    {   t=i;
      while(t>1&&a[i]<=a[t-1])
         t=l[t-1];
         l[i]=t;
    }
    for(i=n-1;i>=1;i--)
    {  t=i;
     while(t<n&&a[i]<=a[t+1])
        t=r[t+1];
        r[i]=t;
    }
    int max=-1;
    for(i=1;i<=n;i++)
    {  if((r[i]-l[i]+1)*a[i]>max)
        max=(r[i]-l[i]+1)*a[i];
    }
    printf("%d\n",max);}
    return 0;
}

最近在接触单调栈,又用栈实现了一下，这里维护一个单增栈,那么如果要进栈的数不能直接入栈,说明当前栈顶比他大,就说明它可以延伸,一直到可以进栈为止,也就是说通过维护单增栈我们一定可以找到左面第一个比他小的和右面第一个比他小的;

还有这里因为矩形的高度可能相同,所以当栈为空时说明可以延伸到头或者尾;

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<stack>
#define N 100010
using namespace std;
int a[N],l[N],r[N];
int main()
{  int n,i;
   while(scanf("%d",&n)!=EOF){
         if(n==0)
        break; 
         stack<long long >st;
         while(!st.empty())
         st.pop();
         l[1]=1;
         st.push(1);
         for(i=1;i<=n;i++)
         scanf("%d",&a[i]);
         for(i=1;i<=n;i++)
         {   
           if(a[st.top()]>=a[i])
             {  while(!st.empty()&&a[st.top()]>=a[i])
                {  
                   st.pop();
                }
                if(st.empty())
                l[i]=1;
                else
                l[i]=st.top()+1;
                st.push(i);
             }
             else
             {  l[i]=i;
                st.push(i);
             }
          
      }
      while(!st.empty())
          st.pop();
          r[n]=n;
          st.push(n);
      for(i=n;i>=1;i--)
      {   
             if(a[st.top()]>=a[i])
               {  while(!st.empty()&&a[st.top()]>=a[i])
                  {   
                      st.pop();
                  }
                  if(st.empty())
                  r[i]=n;
                  else
                  r[i]=st.top()-1;
                  st.push(i);
               }
               else
               {  
                   r[i]=i;
                   st.push(i);
               }
            
           
      }
      //for(i=1;i<=n;i++)
      //printf("%d %d\n",l[i],r[i]);
      long long  ans=0;
      for(i=1;i<=n;i++)
      ans=max(ans,(long long)(r[i]-l[i]+1)*a[i]);
      printf("%lld\n",ans);
    }
    return 0;
}