单调 栈&&队列

题目链接:Largest Rectangle in a Histogram

单调栈:

struct node
{
    int h,id;
    node(int h,int id):h(h),id(id) {}
};

stack<node>S;
int a[100005],l[100005],r[100005];

int main()
{
    int n;
    while(scanf("%d",&n))
    {
        if(n==0)return 0;
        memset(l,0,sizeof(l));
        memset(r,0,sizeof(r));
        for(int i=1; i<=n; i++)
            scanf("%d",&a[i]);
        for(int i=1; i<=n; i++)
        {
            while(!S.empty() && S.top().h>a[i])
            {
                r[S.top().id]=i-S.top().id-1;
                S.pop();
            }
            S.push(node(a[i],i));
        }
        while(!S.empty())
        {
            r[S.top().id]=n-S.top().id;
            S.pop();
        }
        for(int i=n; i>=1; i--)
        {
            while(!S.empty() && S.top().h>a[i])
            {
                l[S.top().id]=S.top().id-i-1;
                S.pop();
            }
            S.push(node(a[i],i));
        }
        while(!S.empty())
        {
            l[S.top().id]=S.top().id-1;
            S.pop();
        }
        ll maxx=0;
        for(int i=1;i<=n;i++)
        {
            ll s=a[i]*((ll)l[i]+(ll)r[i]+1);
            if(s>maxx)maxx=s;
        }
        printf("%lld\n",maxx);
    }
    return 0;
}

题目链接:Imbalanced Array

单调栈:

struct node
{
    int h,id;
    node(int h,int id):h(h),id(id) {}
};

int a[1000005];
int lmax[1000005],rmax[1000005];
int lmin[1000005],rmin[1000005];
stack<node>S;

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);

    //向右拓展<=区间
    for(int i=1; i<=n; i++)
    {
        while(!S.empty() && S.top().h>a[i])
            rmin[S.top().id]=i-S.top().id-1,S.pop();
        S.push(node(a[i],i));
    }
    while(!S.empty())
        rmin[S.top().id]=n-S.top().id,S.pop();

    //向左拓展<区间
    for(int i=n; i>=1; i--)
    {
        while(!S.empty() && S.top().h>=a[i])
            lmin[S.top().id]=S.top().id-i-1,S.pop();
        S.push(node(a[i],i));
    }
    while(!S.empty())
        lmin[S.top().id]=S.top().id-1,S.pop();

    //向右拓展>=区间
    for(int i=1; i<=n; i++)
    {
        while(!S.empty() && S.top().h<a[i])
            rmax[S.top().id]=i-S.top().id-1,S.pop();
        S.push(node(a[i],i));
    }
    while(!S.empty())
        rmax[S.top().id]=n-S.top().id,S.pop();

    //向左拓展>区间
    for(int i=n; i>=1; i--)
    {
        while(!S.empty() && S.top().h<=a[i])
            lmax[S.top().id]=S.top().id-i-1,S.pop();
        S.push(node(a[i],i));
    }
    while(!S.empty())
        lmax[S.top().id]=S.top().id-1,S.pop();

    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=(ll)a[i]*(lmax[i]+1)*(rmax[i]+1)-(ll)a[i]*(lmin[i]+1)*(rmin[i]+1);
    }
    printf("%lld\n",sum);
    return 0;
}

题目链接:Sliding Window

单调队列:

struct node
{
    int val,id;
    node(int val,int id):val(val),id(id) {}
    node(){}
}deq[1000005];

int a[1000005];
int l,r;

int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    l=0,r=0;
    for(int i=1; i<=n; i++)
    {
        while(r>l && a[i]<=deq[r-1].val)
            r--;
        deq[r++]=node(a[i],i);
        if(i<k)continue;
        printf("%d",deq[l].val);
        if(i!=n)printf(" ");
        while(r>l && deq[l].id<=i-k+1)l++;
    }
    l=0,r=0;
    printf("\n");
    for(int i=1; i<=n; i++)
    {
        while(r>l && a[i]>=deq[r-1].val)
            r--;
        deq[r++]=node(a[i],i);
        if(i<k)continue;
        printf("%d",deq[l].val);
        if(i!=n)printf(" ");
        while(r>l && deq[l].id<=i-k+1)l++;
    }
    return 0;
}