单调栈

1：时间复杂度为O（n）

#include<cstdio>
using namespace std;
const int Maxn=1e6+5;
typedef long long LL;
int a[Maxn],stack[Maxn],idx[Maxn],n;
int ()
{
	LL ans=0;int top=0;
	stack[top]=a[0],idx[top++]=0;
	for(int i=1;i<=n;i++)
	{
		if(stack[top-1]>a[i])
		{
			while(top>0 && stack[top-1]>a[i])
			{
				LL tmp=(LL)(i-idx[top-1])*stack[top-1];
				if(tmp>ans) ans=tmp;
				top--;
			}
			stack[top++]=a[i];
		}
		else{
			stack[top]=a[i];
			idx[top++]=i;
		}
	}
	printf("%d",ans);
	return 0;
}
2：时间复杂度为O(nlngn)
#include<stdio.h>
#include<string.h>
#include<math.h>

using namespace std;
#define Maxn 1000005
#define ll long long
int a[Maxn],l[Maxn],r[Maxn],n;
ll ans;
void solve()//上面原理可由乘法原理得到
{
	for(int i=1;i<=n;i++)	l[i]=r[i]=i;//这个是求以这个数为最大的最长区间
    for(int i=2;i<=n;i++)	//取一个负值可求最小
        while(l[i]>1&&a[i]>=a[l[i]-1])l[i]=l[l[i]-1];//now=l[i]
    for(int i=n-1;i>=1;i--)
        while(r[i]<n&&a[i]>a[r[i]+1])r[i]=r[r[i]+1];//注意这里没有等于
    for(int i=1;i<=n;i++)  ans+=(ll)a[i]*(ll)(i-l[i]+1)*(ll)(r[i]-i+1);//加1因为还有本身
    return ;
}
int ()
{
    while(~scanf("%d",&n))
    {
        ans=0;
        for(int i=1;i<=n;i++)	scanf("%d",&a[i]);
        solve();
        for(int i=1;i<=n;i++)	a[i]=-a[i];
        solve();
        printf("%I64dn",ans);
    }
}