【基础算法】单调栈的妙用

1.什么是单调栈

单调栈是一种简单数据结构，顾名思义，就是单调递增（或递减）的栈。

2.单调有什么用？

单调意味着数据是有序的，数据变化是没有“回头路”的，一路走到底，此外，最重要的特性之一就是能够快速地找到最大值或者最小值。

【单调递增性函数图】

【单调递增栈】

3.应用场景

最经典的案例就是运用单调栈在一个序列中求每个元素左边（或右边）第一个比它小（或大）的元素，其实就是求在单调栈中的最值，在遍历过程中时刻维护栈的单调性，那么每个元素对应栈中的最值就是答案。

具体实现可以使用数组模拟栈或者调用库函数（如C++的STL）

4.举个例子

【题目描述】

给出项数为n的整数数列 a1，a2，a3，... ，an。

定义函数 f(i) 代表数列中第i个元素之后第一个大于ai的元素的下标，若不存在，则 f(i)=0。

试求出f(1,2,3,...n)。

【输入格式】

第一行一个正整数n

第二行n个正整数a1,a2,...,an

【输出格式】

一行n个整数f(1,2,...,n)的值。

【输入样例】

5
1 4 2 3 5

【输出样例】

2 5 4 5 0

【数据范围】

1≤n≤3e6, 1≤ai≤1e9

思路：简单来说就是求每一个元素右边第一个比它大的元素下标，符合单调栈的应用场景。由于是求右边的元素下标，因此首先我们需要从右往左遍历，求比它大的元素且从右向左遍历，因此栈中应该保持单调递减性，使用单调递减栈。

样例分析：

【第1步】下标为5的元素是5，栈为空，没有比它大的元素，依题意输出0即可，再将下标5放入栈中（注意下标从1开始）

【第2步】下标为4的元素是3，小于栈顶元素5，满足单调递减性，不需要弹出栈顶，将栈顶下标5放入结果集，再将下标4放入栈中

【第3步】下标为3的元素是2，小于栈顶元素3，满足单调递减性，不需要弹出栈顶，将栈顶下标4放入结果集，再将下标3放入栈中

【第4步】下标为2的元素是4，大于栈顶元素2，不满足单调递减性，弹出栈顶后继续判断，此时栈顶元素为3，仍然不满足单调递减性，因此继续弹出栈顶，新的栈顶元素为5，大于4，（终于）满足单调递减性，不需要弹出栈顶，直接将栈顶下标5放入结果集，再将当前的下标2放入栈中

【第5步】下标为1的元素是1，小于栈顶元素4，满足单调递减性，不需要弹出栈顶，将栈顶下标2放入结果集，再将下标1放入栈中

【第6步】遍历结束，输出结果集

C++代码实现

#include<iostream>
using namespace std;

const int N = 3e6 + 10;

// n为序列长度，sta[]为模拟栈，tt为栈顶指针，a[]为输入序列，res[]存放结果集
int n, sta[N], a[N], tt, res[N];

int main()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i]; //输入序列
    
    for(int i=n; i>=1; i--) //从右往左遍历
    {
        while(tt && a[i] >= a[sta[tt]]) tt --; //栈不能为空的情况下不满足单调性就弹出栈顶
        if(tt) res[i] = sta[tt]; //栈不为空的情况下，将当前栈顶放入结果集
        else res[i] = 0; //若栈为空，说明不存在比当前元素大的元素，依题意将0放入结果集
        sta[++ tt] = i; //动态地将当前元素存入栈中
    }
    
    //可以发现，整个过程都在维护栈的单调性
    
    for(int i=1; i<=n; i++) cout << res[i] << " "; //输出结果，大功告成
    cout << endl;
    
    return 0;
}

5.实战直方图中最大的矩形

来源：《算法竞赛进阶指南》

【题目描述】

直方图是由在公共基线处对齐的一系列矩形组成的多边形。

矩形具有相等的宽度，但可以具有不同的高度。

例如，图例左侧显示了由高度为 2,1,4,5,1,3,3 的矩形组成的直方图，矩形的宽度都为 1:

通常，直方图用于表示离散分布，例如，文本中字符的频率。

现在，请你计算在公共基线处对齐的直方图中最大矩形的面积。

图例右图显示了所描绘直方图的最大对齐矩形。

【输入格式】

输入包含几个测试用例。

每个测试用例占据一行，用以描述一个直方图，并以整数 nn 开始，表示组成直方图的矩形数目。

然后跟随 n 个整数 h1，... ,hn。

这些数字以从左到右的顺序表示直方图的各个矩形的高度。

每个矩形的宽度为 1。

同行数字用空格隔开。

当输入用例为 n=0 时，结束输入，且该用例不用考虑。

【输出格式】

对于每一个测试用例，输出一个整数，代表指定直方图中最大矩形的区域面积。

每个数据占一行。

请注意，此矩形必须在公共基线处对齐。

【输入样例】

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

【输出样例】

8
4000

【数据范围】

1≤n≤1000001≤n≤100000, 0≤hi≤1000000000

思路分析：首先观察直方图很容易发现，每个x坐标对应的矩形条高度就是最大矩形的极限高度，而极限宽度则取决于左边能够延伸到哪里，右边能延伸到哪里。在高度能够确定的情况下，求面积只需要确定最大宽度，而求最值可以使用单调栈的思想。令每个矩形条向左延伸，直至碰到第一个比它矮的矩形条，将其坐标存入左极限集；向右延伸，直至碰到第一个比它矮的矩形条，将其坐标存入右极限集。最后遍历x轴的每个矩形条，求出每个矩形条对应的面积：高度*（右极限-左极限-1），取最大即可。

C++代码实现

#include<iostream>
#include<algorithm>
using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, h[N], l[N], r[N], sta[N]; //l[]为左极限集，r[]为右极限集, sta[]为模拟栈

int main()
{
    while(cin >> n, n)
    {
        h[0] = h[n+1] = -1;
        for(int i=1; i<=n; i++) cin >> h[i];
        
        int tt = 0;
        sta[0] = 0;
        for(int i=1; i<=n; i++) //从左往右遍历，求每个x的左极限
        {
            while(h[i] <= h[sta[tt]]) tt --;
            l[i] = sta[tt];
            sta[++ tt] = i;
        }
        
        tt = 0;
        sta[0] = n + 1;
        for(int i=n; i; i--) //从右往左遍历，求每个x的右极限
        {
            while(h[i] <= h[sta[tt]]) tt --;
            r[i] = sta[tt];
            sta[++ tt] = i;
        }
        
        LL res = 0;
        for(int i=1; i<=n; i++)
            res = max(res, (LL)h[i] * (r[i] - l[i] - 1)); //矩形面积公式
        
        cout << res << endl;
    }
    
    return 0;
}

这里有道力扣的面试题，跟上面的实战题类似，没想到在力扣里的难度是困难题，在竞赛里其实只是一道简单题= =

链接点这里

6.最后的话

上面的C++代码实现中的数组模拟栈可以换成库函数中的栈，思路是一样的。

你学fei了吗？

（转载请注明出处，侵权必究）