HDU 1506【单调栈】

思路：

转化成对于某一位置为最小值求向两边最远>=他的位置，用单调栈就能轻易完成。

那么ans=(left+right)*h[i];

维护单调递增还是递减呢？

我们能很快反应到，一旦碰到一个比他小的元素，那么之前的那个比他大的就要结束了。

ok，大致了解到碰到比他小的元素，那么比他大的呢？

也简单呀，对于比他大的元素，左端点已经找到了呀！

那么基于双方考虑，是不是就是维护单调递增栈呢？

如果碰到比top值大的，那么就压栈，并且左端点为i-1；

如果遇到比top值小的，要把栈里面值比他大的全部输出，因为已经找到右端点 i 了。

这么理解记忆还是略累啊。。。我就是如果我要以他为最小值两边延伸，那么就维护增，记忆成相反的。

而且比较喜欢用结构体表示一个结点所有信息，仅供参考吧~

//#include <bits/stdc++.h>

#include <iostream>

#include <stack>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <vector>

#include <map>

using namespace std;

typedef long long LL;

typedef pair<int,int> PII;

const int N=1e5+10;

struct asd

{

    LL left,right;

    LL w;

};

LL h[N];

LL n;

stack<asd>q;

int main()

{

    while(~scanf("%I64d",&n)&&n)

    {

        asd now,nex;

        while(!q.empty())

            q.pop();

        for(int i=1; i<=n; i++)

            scanf("%I64d",&h[i]);

        LL ans=h[1];

        now.left=0;

        now.right=1;

        now.w=h[1];

        q.push(now);

        for(int i=2; i<=n; i++)

        {

            now.left=0;

            now.right=1;

            now.w=h[i];

            while(!q.empty()&&q.top().w>h[i])

            {

                nex=q.top();

                q.pop();

                now.left+=(nex.left+1);

                LL temp=(nex.left+nex.right)*nex.w;

                ans=max(ans,temp);

                if(!q.empty())

                    q.top().right+=nex.right;

            }

            q.push(now);

        }

        while(!q.empty())

        {

            nex=q.top();

            q.pop();

            LL temp=(nex.left+nex.right)*nex.w;

            ans=max(ans,temp);

            if(!q.empty())

                q.top().right+=nex.right;

        }

        printf("%I64d\n",ans);

    }

    return 0;

}

巴特西

HDU 1506【单调栈】

最新文章

热门文章