关于算法:单调栈模板总结及应用

文章和代码曾经归档至【Github 仓库：https://github.com/timerring/algorithms-notes】或者公众号【AIShareLab】回复 算法笔记 也可获取。

枯燥栈模板

栈：先进后出。

队列：先进先出。

数组模仿栈和队列相较于 STL 的益处在于速度快，尽管在理论编译的时候会有 O2 优化，使两者相差无几，然而在算法题中个别没有优化。

栈算法模板

// 栈定义为 stk[N]，tt 示意栈顶，初始化为 0
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
/*
    if(tt > 0) not empty
    else empty
*/
if (tt > 0)
{}

枯燥栈罕用与给定一个数，寻找在这个序列中每一个数的右边离他最近的且比他小的数在什么中央。

例题：枯燥栈

给定一个长度为 N 的整数数列，输入每个数右边第一个比它小的数，如果不存在则输入 −1。

输出格局

第一行蕴含整数 N，示意数列长度。

第二行蕴含 N 个整数，示意整数数列。

输入格局

共一行，蕴含 N 个整数，其中第 i 个数示意第 i 个数的右边第一个比它小的数，如果不存在则输入 −1。

数据范畴

$1≤N≤10^5$
$1≤$ 数列中元素 $≤10^9$

输出样例：

5
3 4 2 7 5

输入样例：

-1 3 -1 2 2

基本思路

定义一个栈，别离读入数据，而后判断栈中的数字，如果栈顶的数字大于等于读入的 x，则将该数出栈（把大于它的所有数剔除），直到栈顶数字小于该数，输入该数，而后将 x 存入栈顶。这样能够保障栈内的数字始终是一个线性的存储。即输出的 x 能够找到离它最近的比他小的数。

code

# include <iostream>

using namespace std;

const int N = 100010;

int n;
int stk[N], tt;

int main()
{
    cin >> n;
    
    for(int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        while(tt && stk[tt] >= x) tt --; // 如果栈顶元素大于以后待入栈元素，则出栈
        if(tt) cout << stk[tt] << ' '; // 如果栈不空，则该栈顶元素就是左侧第一个比它小的元素
        else cout << -1 << ' '; // 如果栈空，则没有比该元素小的值，输入 -1
        // 再将该元素增加进去
        stk[++ tt] = x;
    }
    
    return 0;
}

尽管这个算法中有两个循环，然而理论针对第二层循环，每个数只会有压入和弹出两个操作，并没有波及到遍历，因而工夫耗费为 2N，工夫复杂度为 O(N)。

同样也能够应用 STL 实现：

#include<iostream>
#include<vector>
using namespace std;
int main() {
    int n,x;
    cin >> n;
    vector<int> t;
    while (n--) {
        cin >> x;
        while (t.size() > 0 and t.back() >= x) {t.pop_back();
        }
        if (t.size() == 0) {cout << -1 << ' ';}else {cout << t.back()<<' ';
        }
        t.push_back(x);
    }
    return 0;
}