$\color{green}{<–画图不易,点下这里赞一下吧}$
视频讲解: https://www.acwing.com/video/5400/
算法原理:
用单调递增栈,当该元素可以入栈的时候,栈顶元素就是它左侧第一个比它小的元素。
以:3 4 2 7 5 为例,过程如下:
代码如下:
//cpp
//参考y总
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N], tt;
int main()
{
int n;
cin >> n;
while (n -- )
{
int x;
scanf("%d", &x);
while (tt && stk[tt] >= x) tt -- ;//如果栈顶元素大于当前待入栈元素,则出栈
if (!tt) printf("-1 ");//如果栈空,则没有比该元素小的值。
else printf("%d ", stk[tt]);//栈顶元素就是左侧第一个比它小的元素。
stk[ ++ tt] = x;
}
return 0;
}
准备应对一大堆复杂公式的时候,这张图让我眼前一亮……
# 大写的赞
#前排感谢大佬
如果有部分同学和我一样,习惯使用STL,看模拟的栈还不是非常熟练的话,我在这里贴一份使用STL的代码供大家使用
you are real heros
这里是栈实现
都用stl了也不用搞个stack吗
兄弟,而你,才是真正的英雄
图好形象,终于明白了 感谢
动画有点快, 看不起 , 我感觉用多几张图片更好
用stl的写法
蛙趣,一张动图解决了我的全部疑惑orzorzorz
非常栈“赞”
orz
海绵宝宝太牛辣!!!
stk[ ++ tt] = x;为什么向栈顶插入一个数 ?
因为这个 x 是最新的数, 有可能比后面小, 插入接着后面的比较
大佬 ,那个图好像看不了了
你是 真英雄,受益匪浅,Orz
为什么不能是stk[tt++]=x呢
看你怎么定义tt了,这里的话tt是先计算tt再赋值,而tt是等赋值结束后再计算tt
作为假这个条件判断,0表示栈内空的,但如果是t++的话,则数组中stk[0]存有数值,是非空的
谢谢你,海绵哥
不是以3 4 2 7 5为例吗,怎么图上是3 4 2 7 9,
!这个动画是怎么做的??太厉害了
GIF
时间复杂度是多少,o(n➕m)?
nb
#include [HTML_REMOVED]
#include [HTML_REMOVED]
using namespace std;
int main()
{
stack[HTML_REMOVED] a;
int n;
cin >> n;
while (n–) {
int x;
cin >> x;
while (a.size() && a.top() >= x) a.pop();//弹出条件:当栈不为空,前一个元素比后一个元素大的时候
if (!a.size()) cout << -1 << ” “;//栈为空,未找到
else cout << a.top() << ” “;//前一个元素就是这个元素的所求
a.push(x);//将元素导入栈
}
}