博客

题目链接：

https://vjudge.net/problem/POJ-2559

以前接触这道题的时候还以为这是单调栈的模板题。但现在觉得单调栈数据结构远比这道题解法好理解得多。

解法：

初次见这道题的话肯定是先分析问题（鬼tm才一开始就确定单调栈是解法）。

首先：按照常规思路，试一试从左到右扫描，每扫到一个位置i，高度为h[i]，计算位置i的贡献attri[i]：当第i个棍一定会被贡献（可以只是贡献一部分高度），而且第i个棍必须是最后面的一个。由于第i个棍贡献不同高度时答案可能会不同，你要找到最大的答案视为attri[i]。由于attr[i]对应的高度h_attr[i]肯定是第i个之前并且小于等于h[i]。也就是说你计算attr[i]时只用考虑前i个中高度小于等于h[i]的就行了。那么第i个考虑进去的时候前面只要比他高的被它踢出数组就可以，每个位置都这样处理的话，数组里面一定是一个非递减序列。这样不就成了单调栈吗。

还没完，其次就是要计算那个attr[i]了，计算attr[i]你有两个选择：choose1.第i个进栈时就计算       choose2.第i个被踢出时计算

此处注意了，我把头想破发现两个方法都得每次把栈扫一遍，时间复杂度不允许

现在把attr[i]定义改一下：第i个的h[i].h[i]所有高度都被贡献上时的最大值。这样一来和之前一样还是要用单调栈。不过计算attr[i]就有了途径：choose2

现在可以考虑怎么计算，既然i被选中了,那么你得考虑i向左连续和向右连续各有多少高度至少为h[i]的。假设i被k踢出了栈，那么必知h[i]>h[k],那么其实i向右连续就有k-i-1个高度至少为h[i]的。至于向左连续设有lenth[i]个，一开始为1（它自身），你想想，假设i之前把j踢出了栈，那么lenth[i]+=lenth[j](此处有点dp思想)，总结那不就是i每踢一个前面比它高的j，那么lenth[i]都得加上length[j]。

向左向右的连续各有多少高度至少为h[i]的有了思路，那么attr[i]不就出来了吗：attr[i]=(lenth[i]+k-i-1)*h[i]     ——i是被k踢出的栈

答案就是：max(attr[i])  {i<n且i>=0}

有一个细节：若要确保attr[i]的i从0到n-1都能考虑得到，你得在最后加上一个最小的高度把前面所有的高度都踢出去。即:h[n]=0;

接下来就是代码实现部分了(PS:可能有人会注意这里有两层循环,想复杂度会不会达到n^2级别,但是内层循环其实是出栈,外层循环控制入栈,每个数都仅入栈出栈最多一次,因此复杂度是O(n)的,也就是说单调栈的构成是O(n)的)：

#include <cstdio>
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
typedef long long ll;
const int max_n=1e5+10;
ll A[max_n];//第i个对应的高度为A[i]
ll sta[max_n];//存储高度的栈
ll len[max_n];//存储上面所讲的length[i]的栈
ll pos[max_n];//存储下标的栈
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n) break;
        for(int i=0;i<n;i++) scanf("%lld",&A[i]);
        A[n]=0;
        int top=0;
        ll ret=0;
        for(int i=0;i<=n;i++)
        {
            int x=1;
            if(top)
            {
                while(top&&sta[top-1]>A[i])
                {
                    ret=max(ret,sta[top-1]*(len[top-1]+i-pos[top-1]-1));
                    x+=len[top-1];
                    top--;
                }
            }
            sta[top]=A[i];
            pos[top]=i;
            len[top++]=x;
        }
        printf("%lld\n",ret);
    }
}