单调栈总结

· · 算法·理论

part 1 引入

例：P1165 日志分析

一眼看上去，像普普通通的栈模版，可是如果仔细看的话，会发现它比栈模版多了一个操作——询问最大值。

Q1：这时问题就有了，怎么解决最大值呢？

A1：我们肯定会想起优先队列。每次输出队头不就行了。好，问题解决了，完结撒花.....诶，等等。

Q2：可是又怎么解决同时出队的问题呢？总不可能遍历一遍整个优先队列吧。

A2：想要访问也可以，得用手写的，每次遍历一遍即可。

Q3：等等，我们算算时间复杂度，询问 O(n)，每次遍历 O(n)，拢共 O(n^2)，一看数据范围，n \le 2 \times 10^5，时间复杂度上又过不去。

A3：我们可以不用优先队列，我们可以构想一个全新的栈，它的栈顶就是普通栈中的最大值，如果当前是弹出操作且普通栈顶的元素与新栈顶的值完全相同，那就同时弹出两个栈的栈顶元素，如果不相同那就只弹出普通栈顶的，我们把这个我们新发明的栈叫什么呢？就叫最大栈吧！

Q4：那怎么入栈呢？

A4：普通栈就直接入，最大的栈顶要存储最大的值，那就只有压入元素大于栈顶元素时再压入吧。哦，对了，注意，还有等于的时候也要进，因为如果普通栈进了两个最大值，最大栈只进了一个，如果普通栈里的弹出一个，最大值依旧是原来的最大值，而最大栈里的就变了。

代码实现：

        cin>>op;
        if(op == 0){
            cin>>x;
            sta1[++top1] = x;
            if(x>=sta2[top2])sta2[++top2] = x;
        }else if(op == 1){          
            if(top2 && sta2[top2] == sta1[top1]){
                top2--;
            }
            if(top1)top1--;
        }else{
            cout<<sta2[top2]<<'\n';
        }

恭喜你，发明了最大栈，因它里面的元素都是单调的，所以又叫单调栈。完结撒花！ 再等等！

part 2 应用

Function 1：寻找一个元素左（右）第一个比它大（小）的元素下标

例题：P5788 【模板】单调栈

其实在应用中，只需一个栈足矣，和模版原理差不多，只是每个元素都会入栈，然后入栈时弹出比它小（大）的元素，来保持单调栈的单调性。然后每次元素进栈前的栈顶元素即是所求元素。整个下来时间复杂度是 O(n)。

代码实现：

    for(int i = n;i>=1;i--){
        if(sta.empty()){
            sta.push(i);
            continue;
        }
        while(!sta.empty() && a[i]>=a[sta.top()])sta.pop();
        if(!sta.empty())ans[i] = sta.top();
        sta.push(i);
    }
    for(int i = 1;i<=n;i++)cout<<ans[i]<<" ";

Function 2：发射站模型(求点对数量)

例题：P1901 发射站

这种类型的题目看似复杂，实则简单，其实只是让我们对于每一个 a_i 求前后的第一个大（小）于这个数的下标 j_1 和 j_2，然后再统计答案。很多题目也是这样，变化多端，但是万变不离其宗，只要看清它的本质，其实就很简单了。

代码实现：

    for(int i = n;i>=1;i--){
        while(!s.empty() && a[i]>=a[s.top()])s.pop();
        if(!s.empty())ans1[i] = s.top();
        s.push(i);
    }
    while(!s.empty())s.pop();
    for(int i = 1;i<=n;i++){
        while(!s.empty() && a[i]>=a[s.top()])s.pop();
        if(!s.empty())ans2[i] = s.top();
        s.push(i);
    }
    for(int i = 1;i<=n;i++){
        z[ans1[i]]+=v[i];
        z[ans2[i]]+=v[i];
    }
    long long maxnn = 0;
    for(int i = 1;i<=n;i++){
        maxnn = max(maxnn,z[i]);
    }
    cout<<maxnn;

Function 3：寻找板块填充最小矩形数/最大矩形面积

例题：P3467 [POI 2008] PLA-Postering

这里分三点讨论：

1.当前元素大于栈顶元素

没有变动，直接入栈。

2.当前元素等于栈顶元素

直接合并为一个元素，以后再操作。

3.当前元素小于栈顶元素

当前板块直接单独用一个矩形，计数器加一。

最后栈中残留的每一个元素都单独用一个矩形，输出答案即可。

代码实现：

    int ans = 0;
    for(int i = 1;i<=n;i++){
        while(!s.empty() && a[i]<=a[s.top()]){
            if(a[i]<a[s.top()]){
                ans++;
            }
            s.pop();
        }
        s.push(i);
    }
    while(!s.empty())ans++,s.pop();
    cout<<ans;

完结撒花~~~

以上只是单调栈的三种用法，简单记录一下。