单调栈

1 入门题目:【模板】单调栈

https://www.luogu.com.cn/problem/P5788

一句话题题目意思:求每个元素 $i$ 后面的第一个大于 $a[i]$ 的第一个位置 $j$

朴素的暴力算法是 $o(n^2)$ ,但给的数据范围要求 $O(n)$ 内解决

想一想我们,一个一个读取数据,然后类似插入排序一样,在维护一个有序的序列


  +-+
  | |                   x
  | |                  +-+
  | |                  | |
  | |                  | |
  | | +-+              | |
  | | | | +-+          | |
  | | | | | | +-+      | |
  | | | | | | | |      | |
--+-+-+-+-+-+-+-+------+-+--
                       last

根据[[缩小放大法]],可以轻易的想到如果序列是一个单调下降的,那么每个一元素没有没有后续的"结果".

再给一个很高的柱子放在最后面,那么前面单调下降的所有的且小于 $x$ 的柱子都应该投影到last柱子上.

那么这些"投影"到last上的柱子就有了答案,就把可以它们去除了,最后变成如图下


  +-+
  | | x
  | |+-+
  | || |
  | || |
  | || |
  | || |
  | || |
  | || |
--+-++-+--
     last

建立一个栈
栈内准备添加一个位置last,值为x
所有比x小的栈,都出栈,并记录这些点的答案
入栈last

伪代码如下:

1:Stack mysta;

2:int a[maxn];

3:int ans[maxn];

4:for $i=1$ to $n$ do

5:while $a[mysta.top()] \leqslant a[i]$ or not $mysta.empty()$ do

6:ans[mysta.top()] = i;

7: $a.pop()$

8:end while

9: $mysta.push(i)$ ;

10:end for

11:for $i=1$ to $n$ do

12:print ans[i];

13:end for

可以想到栈内的元素一定是单调不上升的.

时间负责度: 每个点最后入栈一次,出栈一次,所以时间为 $O(n)$

算法

核心思想: 去除那些已经得到答案的点,自然形成单调.

1.1 代码

/* author: Rainboy email: rainboylvx@qq.com
 * time: 2023年 06月 12日 星期一 16:04:42 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e6+5,maxe = 1e6+5; //点与边的数量

int n,m;
/* 定义全局变量 */

int a[maxn]; //每个位置的值
int ans[maxn]; //存答案

//栈的模板
template<typename T = int,int siz = maxn>
struct mystack{
    T sta[siz+5];
    int head = 0;

    void clear() { head = 0;}

    void push(T a) { sta[head++] = a;}

    void pop(){head--;}

    T top() { return sta[head-1];}

    bool empty() { return head == 0;}

    int size() { return head;}
};

mystack<int> sta; //创建一个栈



int main(int argc,char * argv[]){

    cin >> n;

    for(int i=1;i<=n;++i) cin >> a[i];

    for(int i=1;i<=n;++i){
        int t = a[i];
        while( !sta.empty() && a[sta.top()] < t){
            // 记录sta.top()位置投影到的位置
            ans[sta.top()] = i;
            sta.pop();
        }
        sta.push(i); //把位置入栈
    };


    //输出答案
    for(int i=1;i<=n;++i) cout << ans[i] << " ";
    std::cout << "\n";

    return 0;
}

2 题目2: 直方图中最大的矩形

题目地址: roj 3032: 「Largest Rectangle in a Histogram」直方图中最大的矩形

3 解析

已知

由题目数据 $n \leqslant 10^5$ 知,算法应该是扫一遍就能得答案,
设 $f(i)$ 表示可以整体问题可以转化成: $\max(f(i)),i \leqslant n$

根据我思维方式里的缩小放大法的思维方式,

3.1 情况1: 高度一样

首先想到: 情况1: 如果所有的矩形的高度都一样,显然可以直接用矩形的数量乘以高度作为答案.这个问题变成十分简单.

3.2 情况2: 高度有序

情况2:矩形的高度从左到右单调增加.给每个矩形编号如下图

以 $i$ 为开头的面积为: 矩形 $i$ 向右投影的面积: $(4-i-1) * height_i$ ,这样只需要扫一遍数组就可以得到答案,时间为 $O(n)$ .

说明

那么以矩形 $i$ 为结尾如何求最值大面积值呢?此时我们想要考虑向左投影.考虑最后一个矩形 $4$ ,它对 $1,2,3$ 的贡献如下

说明

当矩形 $4$ 对前面的贡献的高度,越来越低.

我们用如下的伪代码来描述我们的思想

1: $w \gets 0$

2:for $i = 4$ to $1$ do

3: $w \gets w + 1$

4: $ans \gets \max(ans, w \times height_i)$

5:end for

6:print $ans$

可以想到: 我们不停的从后向前扫描矩形,然后维护一个宽度为 $w$ ,高度不停降低的矩形(共享).也可以这样理解:我们不停的删除矩形上部的无用的部分.

于是我们得到一个结论:当数据是有序时,我们可以轻松的解决题目,时间 $O(n)$

3.3 情况3: 数据是无序

根据集合的分类思想黑白气球,如果我们能不漏的(可以重复)求出所有的以第 $i$ 矩形为结尾向左投影面积,那么就可以解决这个最值问题.

x左边的矩形,是单调减的,这就是情况2.

以上图的 $x$ 矩形,如果要求出x向左投影的所有面积,显然左边的所有的比 $x$ 高的部分都没有意义,全部删除,维护一个高度为 $height_x$ 的大矩形.

x右侧的比较x高的矩形,例如 $y$ ,它的投影经过 $x$ 时,高度会变成 $x$ 的高度,也就说:x的删除操作不会影响到y的投影面积求取.和光的投影一样.

如果 $height_y < height_x$ ,那不就是上面说的?

因为y后的单调增加,还是变成了情况2-1.在最后求出一个单调上长的矩形.

新出现的一个矩形 $z$ ,它的高度有两种情况:

比前面的高
比前面的低

无论哪种情况,我们总是能转化为已知的操作来做.

以第i个矩形向右投影,就可以得到以第i个矩形为开头的面积了.

反过来思考,如果矩形是单调减的,那只要考虑以第i个矩形为结尾就可以了.

证明:按上面的操作,不漏: 即,问题 $f(i)$ 以i为结尾的向左投影面积

然后认识到这种操作就是栈上的操作,于是用了栈来维护.

算法

核心思想:

截取
截取不会影响对后面的贡献

4 代码实现

/* author: Rainboy email: rainboylvx@qq.com
 * time: 2023年 06月 12日 星期一 21:21:31 CST */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+5,maxe = 1e6+5; //点与边的数量

ll n,m;
ll a[maxn];
/* 定义全局变量 */

//栈的模板
template<typename T = int,int siz = maxn>
struct mystack{
    T sta[siz+5];
    int head = 0;

    void clear() { head = 0;}

    void push(T a) { sta[head++] = a;}

    void pop(){head--;}

    T top() { return sta[head-1];}

    bool empty() { return head == 0;}

    int size() { return head;}
};

struct node {
    ll h; //高度
    ll w; //宽度
};

//求矩形a的面积
ll area(node &a) {
    return a.h * a.w;
}

mystack<node> sta; //创建一个栈

int main(){

    while(1) {
        cin >> n;
        ll ans = -1;

        if( n == 0 ) break;
        sta.clear(); //清空栈
        for(int i = 1;i <= n ;++i ) // 读取数据
            cin >> a[i];
        for(int i=1;i<=n;++i){
            node t = {a[i],1};

            //把比当前高的都删除
            while(!sta.empty() && sta.top().h >= t.h )
            {
                t.w += sta.top().w;
                sta.pop();
            }
        }

        //清空sta里的值
        std::cout << ans << "\n";
    }
    return 0;
}

5 相关题解

暂无相关题解