普通栈就5个操作
#include<stack> 0.stack<类型> 名字; 创建 1.名字.push(元素); 压入栈变为新的栈顶 2.m=名字.top(); 获取栈顶元素 3.名字.pop() ; 弹出栈顶元素 4.length=名字.size() 获取栈内元素长度
ps: 对于 顺序栈和链栈 相对于普通栈来说 效率会相对高一点
(普通栈考虑太多东西从而使效率降低 而对某一专一问题用顺序栈 和 链栈 就可以解决效率高些嘛... )
然后 三类题目;
1.最基础的应用就是给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数。 poj3250
2.给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。poj2559
3.给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。poj3494
小生不才,百思不得其解.....于是偷瞄答案..我去还可以酱紫~;
1.poj3250
仔细看看大神代码
//为什么会超过int型…… #include<stdio.h> #include<string.h> #include<iostream> #include<stack> #define inf 0x3f3f3f3f using namespace std; typedef long long LL; int main() { int i,n,top,a[80010]; //top指向栈顶元素 LL ans; //存储最终结果 stack<int> st; //st为栈，每次入栈的是每头牛的位置 while(~scanf("%d",&n)) { while(!st.empty()) st.pop(); //清空栈 for(i=0;i<n;i++) scanf("%d",&a[i]); a[n]=inf; //将最后一个元素设为最大值 ans=0; for(i=0;i<=n;i++) { if(st.empty()||a[i]<a[st.top()]) { //如果栈为空或入栈元素小于栈顶元素，则入栈 st.push(i); } else { while(!st.empty()&&a[i]>=a[st.top()]) { //如果栈不为空并且栈顶元素不大于入栈元素，则将栈顶元素出栈 top=st.top(); //获取栈顶元素 st.pop(); //栈顶元素出栈 //这时候也就找到了第一个比栈顶元素大的元素 //计算这之间牛的个数，为下标之差-1 ans+=(i-top-1); } st.push(i); //当所有破坏栈的单调性的元素都出栈后，将当前元素入栈 } } printf("%lld\n",ans); } return 0; }
#include<iostream> #include<cstring> #include<cmath> #include<stack> #define inf 0x3f3f3f3f using namespace std; int map[80005]; stack <int > num; int main() { int n; long long sum; while(cin>>n) { map[n]=1000000000; sum=0; for(int i=0; i<n; i++) cin>>map[i]; while(!num.empty()) num.pop(); for(int i=0; i<=n; i++) { if(num.empty()||map[num.top()]>map[i]) { num.push(i); } else { while(!num.empty()&&map[num.top()]<=map[i]) { sum+=(i-num.top()-1); num.pop(); } num.push(i); } } cout<<sum<<endl; map[n]=0; } return 0;
2.poj2559
这个要好好看 ,我是真没看懂
用纸和笔推演了一遍才看明白
(最好能自己推...看我写的注意点..容易变傻(我都感觉太细了))
#include<stdio.h> #include<string.h> #include<iostream> #include<stack> using namespace std; typedef long long LL; int main() { int i,n,top; //top指向栈顶 stack<int> st; //栈用于保存矩形的编号，即位置 LL tmp,ans,a[100010]; //tmp为临时变量，记录面积的值，ans为结果，记录最大面积值 while(~scanf("%d",&n)&&n) { for(i=0;i<n;i++) scanf("%lld",&a[i]); ans=0; a[n]=-1; //最后一个元素设为最小值，以最后清空栈 for(i=0;i<=n;i++) { if(st.empty()||a[i]>=a[st.top()]) { //如果栈为空或入栈元素大于等于栈顶元素 ，则入栈 st.push(i); } else { while(!st.empty()&&a[i]<a[st.top()]) { //如果栈非空且入栈元素小于栈顶元素，则将栈顶元素出栈 top=st.top(); st.pop(); tmp=(i-top)*a[top]; //在出栈过程中计算面积值 if(tmp>ans) ans=tmp; //更新面积最大值 } st.push(top); //只将可以延伸到的最左端的位置入栈 a[top]=a[i]; //并修改该位置的值 } } printf("%lld\n",ans); } return 0; }
#include<iostream> #include<cstring> #include<stack> #include<cmath> #include<cstdio> using namespace std; long long a[100005]; stack <int > num; int main() { int n,top; long long ans,tmp; while(~scanf("%d",&n)&&n) { for(int i=0; i<n; i++) scanf("%lld",&a[i]); ans=0; a[n]=-1; while(!num.empty()) num.pop(); for(int i=0; i<=n; i++) { if(num.empty()||a[num.top()]<=a[i]) num.push(i); else { while(!num.empty()&&a[num.top()]>a[i]) { top=num.top(); num.pop(); tmp=(i-top)*a[top]; ans=max(tmp,ans); } num.push(top); a[top]=a[i]; } } printf("%lld\n",ans); } return 0; }
注意点:
0.我用C++写的 tle 了几次 可能要用scanf() 以及printf();
wr a[]数组没有用long long ;然后终于..AC!
1.由于咱们这个 栈是单调递增的所以后面的元素一定大于前面的;
酱紫就意味着 i到top(这个是栈顶元素也就是a的下标吧)之间的数据的公共部分是a[top];
也就是tmp 是目前的的 公共面积值;
2.更新单调栈内元素 只要把最后一个大于a[i] 的下标送进去也就是top
然后把 a[top]更新为新的最小的值a[i]至于原因吗:因为到i为止最大的就是他了....
相当于更新 新的单调递增栈 ; 其次就是我们要用距离 * 最小值=tmp所以
一定要将i能变成的a的最小的下标加入到单调栈中去嘛~可以当作x-y坐标系来看这个题;
3.poj3494
这个就是先扫一遍用上一行的状态来对下一行进行更新最终变为 第二种也就是poj2559解题的形式
感觉很巧,大神思路很すごい
感觉还是看我的代码吧.....自己看思路写的..你仔细研究过2559应该能看懂吧...大神代码有解析
博主代码题解
然后附上大神解析 单调栈 链接
原文：https://www.cnblogs.com/maxv/p/10883643.html
