单调栈思维导图
单调栈
树图思维导图提供 单调栈 在线思维导图免费制作，点击“编辑”按钮，可对 单调栈 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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; }
相关思维导图模板
树图思维导图提供 仙剑奇侠传之新的开始-客栈（9级开启） 在线思维导图免费制作，点击“编辑”按钮，可对 仙剑奇侠传之新的开始-客栈（9级开启） 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：f4b4977c39b236814587d1f8189260f6
树图思维导图提供 栈和队列的应用思维脑 在线思维导图免费制作，点击“编辑”按钮，可对 栈和队列的应用思维脑 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：a1fbcbaa0d1a723bbeca8cfdb13cfea7
沪公网安备 31011502019485号
上海工商