单调栈

一系列数寻找一个子序列，子序列的长度乘以子序列中的最小值使得这个值最大

Hdu 1506 Largest Rectangle in a Histogram

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll h[100100];
ll R[100100];
ll L[100100];
stack<ll> s;
int main( )
{
      int n;
      while(cin>>n&&n)
      {
            while(!s.empty( ))
            {
                  s.pop( );
            }
            for(int i=0;i<n;i++)
            {
                  cin>>h[i];
            }
            for(int i=0;i<n;i++)
            {
                  while(!s.empty( )&&h[s.top( )]>=h[i])
                  {
                        s.pop( );
                  }
                  if(s.empty( ))
                  {
                        L[i]=0;
                  }
                  else
                  {
                        L[i]=s.top( )+1;
                  }
                  s.push(i);
            }
            while(!s.empty( ))
            {
                  s.pop( );
            }
            for(int i=n-1;i>=0;i--)
            {
                  while(!s.empty( )&&h[s.top( )]>=h[i])
                  {
                        s.pop( );
                  }
                  if(s.empty( ))
                  {
                        R[i]=n;
                  }
                  else
                  {
                        R[i]=s.top( );
                  }
                  s.push(i);
            }
            ll ans=-1;
            for(int i=0;i<n;i++)
            {
                  ans=max(ans,h[i]*(R[i]-L[i]));
            }
            cout<<ans<<endl;
      }
      return 0;
}