单调栈

id: monotonic_stack

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

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

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

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

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


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

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

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

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


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

伪代码如下:

\begin{algorithm}
\begin{algorithmic}
\STATE Stack mysta;
\STATE int a[maxn];
\STATE int ans[maxn];
\FOR{$i=1$ \TO $n$}
    \WHILE{$ a[mysta.top()] \leqslant a[i]$ \OR \NOT $mysta.empty()$ }
      \STATE ans[mysta.top()] = i;
      \STATE $a.pop()$
    \ENDWHILE
    \STATE $mysta.push(i)$;
\ENDFOR
\FOR{$i=1$ \TO $n$}
    \Print ans[i];
\ENDFOR
\end{algorithmic}
\end{algorithm}

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

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

一句话算法

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

代码

/* 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: 直方图中最大的矩形

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

解析

已知

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

根据我一[[…/…/mind_theory/|放大缩小]]法的思维方式,

情况1: 高度一样

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

情况2: 高度有序

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

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

::: line :::

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

::: line :::

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

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

\state w=0
\for{$i=4$ \TO $1$}
    \state w++;
    \state ans = max(ans,$w \times height_i$) 
\endfor
\print ans

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

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

情况3: 数据是无序

根据集合的分类思想[[../../enumerationg_permutations/|pair_number],如果我们能++不漏++的(可以重复)求出所有的以第ii矩形为结尾向左投影面积,那么就可以解决这个最值问题.

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

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

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

如果heighty<heightxheight_y < height_x,那不就是上面说的?

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

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

  • 比前面的高
  • 比前面的低

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

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

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

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

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

一句话算法

核心思想:

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

代码实现

/* 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;
}