【C++】Day17单调栈AcWing830.单调栈（算法基础课笔记）

AcWing 830、单调栈 （算法基础课笔记）

一、题目&解读

1、题目2、题目解读 二、思路

1、判断条件 三、AC代码四、总结

---

前言
你好阿，我最近在学acwing的算法基础课，备战蓝桥杯，如果你也是一样的话，欢迎一起学习~

---

一、题目&解读 1、题目

题目链接{点击跳转}

2、题目解读

输出每个数左边第一个比它小的数 ，符合单调栈的模板
单调栈：相当于一个容器 存储的数据具有单调性 如果不符合的数据将会被弹出。

算法模板

常见模型：找出每个数左边离它最近的比它大/小的数int tt = 0;for (int i = 1; i <= n; i ++ ){ while (tt && check(stk[tt], i)) tt -- ; stk[ ++ tt] = i;}

二、思路

借用老哥的图

1、判断条件

该题的判断条件如下：
top &&stk[top]>=x :如果栈顶大于x 则将栈顶弹出

三、AC代码

时间复杂度O(n)

#include using namespace std;const int N = 100010;int stk[N], top;int main () { int m; cin >> m; while (m --) { int x; scanf("%d", &x); while (top &&stk[top]>=x) top--; //如果栈顶小于x 或者栈顶为空则弹出栈顶 if (!top) printf("-1"); else printf("%d", stk[top]); stk[++top] = x; //更新栈顶 } return 0;}

四、总结

学数据结构 最主要的还是要画图，先画一遍，代码自然就能够写了。

结尾：

感谢你能看完，希望对你有帮助 ，如有错误欢迎指正，码字不易，给个赞呗