蒟蒻的第一篇专题……

最近(两天)都在研究单调栈，一开始学单调栈是看这篇文章学的

传送门


ps:顺便吐槽一下单调队列那一题，用g++和stdio交会tle，用c++或者用iostream输出都能ac，估计是poj那个老旧的评测机的锅

概述

单调栈是用来干什么的呢？那篇博文讲得不错

单调是一种思想，当我们解决问题的时候发现有许多冗杂无用的状态时，我们可以采用单调思想，用单调队列或类似于单调队列的方法去除冗杂状态，保存我们想要的状态

单调栈和单调队列十分类似，都采用了单调思想来去除一些冗余状态，但我一开始没有搞懂单调栈在实际运用中所起到的作用

菜鸡的假算法(本人反思)

拿POJ3250做例子，一开始我没有完全理解单调栈的时候做了一遍，并且AC了【证明这题题有点水，贴上错误示例

#include<cstdio>

long long h[100011],s[100011],val[100011],top = 0;
long long n,ans = 0;
int main()
{
    scanf("%lld",&n);
    for (int i = 0;i < n;++i)
    {
        scanf("%lld",h + i);
        while (h[i] >= h[s[top]] and top > 0) 
        {
            top--;
            val[top] += val[top + 1];
            ans += val[top + 1];
        }
        val[top]++;
        s[++top] = i;
        val[top] = 0;
    }
    while (top > 0) 
    {
        top--;
        val[top] += val[top + 1];
        ans += val[top + 1];
    }
    printf("%lld",ans);
    return 0;
}

当时我是这样想的……【翻草稿ing

建一个单调递减栈，开一个val数组记录每只牛能看到多少只牛，一个数在入栈之前将原本的栈顶记录的数+1(因为这个数比之前的栈顶小)，在出栈时把自己记录的数给下一层(因为这层能看到的下一层必定能看到)，这里就不放图了

这个假算法对于这一道题确实能过，然而下一题就不一样了……

这题我一开始是想dp的，但因为刚学单调栈，所以就尝试用单调栈做

但这题用回我的假算法做就不一样了，因为这题比上一题复杂了，错误示范不讲详细过程，最后我推出了一条”状态转移方程”

对于每一个栈:





a

n

s

=

m

a

x

(

s

t

a

c

k

[

i

]

⋅

(

i

d

[

t

o

p

]

−

i

d

[

i

−

1

]

)

)

ans=max(stack[i]·(id[top]-id[i-1]))






a


n


s




=








m


a


x


(


s


t


a


c


k


[


i


]


⋅




(


i


d


[


t


o


p


]




−








i


d


[


i




−








1


]


)


)

好吧，我相信大佬们一眼就看出来这TLE了，然而可怜的我不太会算时间复杂度

这次错误代码也不贴了

真正的单调栈

经过了一个上午的折腾(期间我改了一下思路，写了个WA的程序，用上述TLE程序对拍，结果把WA程序改对之后也TLE了，也就是花了一个上午时间写了一个我写了10多分钟的程序)，我终于发现单调栈除了单调性之外还有其它的特性,例如数列



{

93

,

10

,

40

,

85

,

47

,

19

,

56

}

\{93,10,40,85,47,19,56\}






{



9


3


,




1


0


,




4


0


,




8


5


,




4


7


,




1


9


,




5


6


}






模拟一次单调递减栈

先将93和10入栈

将40入栈，发现此时栈顶元素比40小，将10出栈，再将40入栈

将85入栈，同理先将40退栈，后面47，19可以直接入栈

最后将56入栈，同理将top减到2再入栈

这就是整个

从左到右

的入栈次序了，有一些比较聪明的人可能已经看出id之间的关系，像我这么蠢的人联系一下上面那条式子应该也能想到一些东西

因为出栈的都是比当前栈顶小的数，我们只需要比较一下

入栈前

的栈顶id和

准备进栈

的id，也就是



i

−

i

d

[

t

o

p

]

−

1

i – id[top] – 1






i




−








i


d


[


t


o


p


]




−








1





，就能轻松地得到在当前元素

左边

比其小的元素个数了

知道了这件事，我们只要从左到右扫一遍，再反过来扫一遍，就能知道每一个元素的左右两边一共有多少个比它大(小)的元素了

回到HDU-1506，我们要找到每一个元素左右两边有多少比它大的元素，这样才能以目前元素为高建立一个长方形

#include<cstdio>
#include<cstring>

long long stack[100011],id[100011],h[100011],ans1[100011],ans2[100011],top = 0;

int main()
{
    long long n,ans;
    while (~scanf("%lld",&n) and n != 0)
    {
        ans = 0,top = 0;
        memset(ans1,0,sizeof(ans1));
        memset(ans2,0,sizeof(ans2));
        id[0] = 0;
        for (int i = 1;i <= n;++i)
        {
            scanf("%lld",h + i);
            while (top > 0 and stack[top] >= h[i]) top--;
            ans1[i] = i - id[top];
            stack[++top] = h[i];
            id[top] = i;
        }
        top = 0;
        id[0] = n + 1;
        for (int i = n;i >= 1;--i)
        {
            while (top > 0 and stack[top] >= h[i]) top--;
            ans2[i] = id[top] - i;
            stack[++top] = h[i];
            id[top] = i;
        }
        for (int i = 1;i <= n;++i)
        {
            ans = max(ans,(ans1[i] + ans2[i] - 1) * h[i]);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

代码在这了，记住用LL哦

再给出POJ-3250的正解(虽然上面那个也能AC)

#include<cstdio>

long long h[100011],s[100011],top = 0;

long long n,ans = 0;
int main()
{
    scanf("%lld",&n);
    for (int i = 0;i < n;++i)
    {
        scanf("%lld",h + i);
        while (top > 0 and h[i] >= s[top]) top--;
        ans += top;
        s[++top] = h[i];
    }
    printf("%lld",ans);
    return 0;
}

HDU-1506


POJ-3250

练习

POJ-2796 Feel Good


代码在下面(会折叠的大佬教我一下？)





\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad













WA的话……

试试全是0的话会输出什么←反正我被坑了

\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad
















\quad

#include<cstdio>
#define max(a,b) (a > b ? a : b)
long long stack[100011],id[100011],top,l[100011],r[100011],a[100011],sum[100011];
long long ans,al = 1,ar = 1;
int main()
{
    int n;
    scanf("%d",&n);
    top = 0,id[0] = 0,ans = 0;
    for (int i = 1;i <= n;++i)
    {
        scanf("%lld",a + i);
        sum[i] = a[i] + sum[i - 1];
        while (top > 0 and a[i] <= stack[top]) --top;
        l[i] = id[top] + 1;
        stack[++top] = a[i];
        id[top] = i;
    }
    top = 0,id[0] = n + 1;
    for (int i = n;i >= 1;--i)
    {
        while (top > 0 and a[i] <= stack[top]) --top;
        r[i] = id[top] - 1;
        stack[++top] = a[i];
        id[top] = i;
    }
    for (int i = 1;i <= n;++i)
    {
        long long tot = a[i] * (sum[r[i]] - sum[l[i] - 1]);
        if (tot > ans)
        {
            ans = tot;
            al = l[i],ar = r[i];
        }
    }
    printf("%lld\n%lld %lld",ans,al,ar);
    return 0;
}