笔灵AI论文写作三步搞定，GO>>
单调栈思维导图
免费下载
免费使用文件
Mr.Xu 浏览量：22023-07-15 17:55:47
已被使用0次
单调栈
树图思维导图提供 单调栈 在线思维导图免费制作，点击“编辑”按钮，可对 单调栈 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：2ad5c39eca49660adeaa4b90155922b3
思维导图大纲
单调栈思维导图模板大纲
应用场景
给定一个序列，找序列中的每一个数，左边(右边)离它最近的比它小(大)的数在哪里
例题
找x个左边第一个小于x的数
方法
把第i个数之前的值都放进栈中 从栈顶开始找
但这样还是有点浪费空间，我们还可以优化优化
如果a[top]>=b[i] (i在最右边)，则栈顶可以删掉(原因:对后面的数来说，b[i]有可能是解，但a[top]一定不是)b[i]一直和栈顶判断，直到找到一个栈顶满足a[top]<b[i]，第i个数b[i]可以放进栈顶
#include<bits/stdc++.h> using namespace std; stack<int> s; int main(){ int n,xs; s.push(-1); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&x); while(s.top()>=x) s.pop(); cout<<s.top()<<" "; s.push(x); } return 0; }
沪公网安备 31011502019485号
上海工商