单调栈模板总结及应用

2023-05-13
山东
本文字数：1160 字
阅读完需：约 4 分钟

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

单调栈模板

栈：先进后出。

队列：先进先出。

数组模拟栈和队列相较于 STL 的好处在于速度快，虽然在实际编译的时候会有 O2 优化，使两者相差无几，但是在算法题中一般没有优化。

栈算法模板

// 栈定义为stk[N]，tt表示栈顶，初始化为0int 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 \leq N \leq 1 0^{5}$ $1 \leq$ 数列中元素 $\leq 1 0^{9}$

输入样例：

53 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;}

复制代码

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/a2e6d16e398ffcd6dbac58c37】。未经作者许可，禁止转载。

timerring

关注

公众号【AIShareLab】 2022-07-14 加入

他日若遂凌云志

发布

暂无评论

创作场景

单调栈模板总结及应用

单调栈模板

栈算法模板

例题：单调栈

基本思路

code

timerring

评论