普通栈就5个操作
#include<stack> 0.stack<类型> 名字; 创建 1.名字.push(元素); 压入栈变为新的栈顶 2.m=名字.top(); 获取栈顶元素 3.名字.pop() ; 弹出栈顶元素 4.length=名字.size() 获取栈内元素长度
ps: 对于 顺序栈和链栈 相对于普通栈来说 效率会相对高一点
(普通栈考虑太多东西从而使效率降低 而对某一专一问题用顺序栈 和 链栈 就可以解决效率高些嘛... )
然后 三类题目;
1.最基础的应用就是给定一组数，针对每个数，寻找它和它右边第一个比它大的数之间有多少个数。 poj3250
2.给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列的长度最大。poj2559
3.给定一序列，寻找某一子序列，使得子序列中的最小值乘以子序列所有元素和最大。poj3494
小生不才,百思不得其解.....于是偷瞄答案..我去还可以酱紫~;
0.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 ",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;
1.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 ",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 ",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坐标系来看这个题;
2.poj3494
这个就是先扫一遍用上一行的状态来对下一行进行更新最终变为 第二种也就是poj2559解题的形式
感觉很巧,大神思路很すごい 大神图解
感觉还是看我的代码吧.....自己看思路写的..你仔细研究过2559应该能看懂吧...大神代码有解析
#include<iostream> #include<cstring> #include<stack> #include<cmath> #include<cstdio> using namespace std; stack<int > num; int a[2005][2005]; int m,n,ans; int sta(int x) { int tmp,top; while(!num.empty()) num.pop(); for(int i=0; i<=n; i++) { if(num.empty()||a[x][num.top()]<=a[x][i]) num.push(i); else { while(!num.empty()&&a[x][num.top()]>a[x][i]) { top=num.top(); num.pop(); tmp=(i-top)*a[x][top]; ans=max(tmp,ans); } num.push(top); a[x][top]=a[x][i]; } } return 0; } int main() { while(cin>>m>>n) { ans=0; for(int j=0; j<n; j++) scanf("%d",&a[0][j]); a[0][n]=-1; for(int i=1; i<m; i++) { for(int j=0; j<n; j++) { scanf("%d",&a[i][j]); if(a[i-1][j]&&a[i][j]) a[i][j]+=a[i-1][j]; } a[i][n]=-1; } /* for(int i=0; i<m; i++) { for(int j=0; j<=n; j++) cout<<a[i][j]<<" "; cout<<endl; }*/ for(int i=0; i<m; i++) sta(i); cout<<ans<<endl; } return 0; }
#include<stdio.h> #include<string.h> #include<iostream> #include<stack> using namespace std; int main() { //top指向栈顶；tmp为临时变量，记录面积的值；ans为答案，记录面积的最大值 int i,j,m,n,x,top,tmp,ans,h[2020],a[2020]; stack<int> st; //单调栈，记录位置 while(~scanf("%d%d",&m,&n)) { ans=0; memset(h,0,sizeof(h)); //用于第一行的处理 for(i=0;i<m;i++) { //扫描每一行 for(j=1;j<=n;j++) { scanf("%d",&x); if(x==1) h[j]=h[j]+1; //如果是1，则在上一行本列的基础上+1 else h[j]=0; //否则为0 a[j]=h[j]; //a数组用来向左右扩展 } a[n+1]=-1; //设最后元素为最小值，以最后让栈内元素出栈 for(j=1;j<=n+1;j++) { if(st.empty()||a[j]>=a[st.top()]) { //如果栈为空或入栈元素大于等于栈顶元素，则入栈 st.push(j); } else { while(!st.empty()&&a[j]<a[st.top()]) { //如果栈非空并且入栈元素小于栈顶元素，则将栈顶元素出栈 top=st.top(); st.pop(); tmp=(j-top)*a[top]; //计算面积值 if(tmp>ans) ans=tmp; //更新面积最大值 } st.push(top); //将最后一次出栈的栈顶元素延伸并入栈 a[top]=a[j]; //修改其对应的值 } } } printf("%d ",ans); } return 0; }
3.poj2796
......心态也就呢样了....
个人解析在下面...也就理解理解了....感觉就会说句 なるほど
#include<stdio.h> #include<iostream> #include<stack> using namespace std; typedef long long LL; int main() { int i,n,pos1,pos2; //pos1和pos2记录区间的开始和结束位置 //tmp为临时变量，记录区间内的和；top指向栈顶元素；ans为结果；sum为前缀和 LL tmp,top,ans,a[100010],sum[100010]; stack<int> st; //单调栈，记录元素位置 while(~scanf("%d",&n)) { while(!st.empty()) st.pop(); //清空栈 sum[0]=0; for(i=1;i<=n;i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; //计算前缀和 } a[n+1]=-1; //将最后一个设为最小值，以最后让栈内元素全部出栈 ans=0; for(i=1;i<=n+1;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=sum[i-1]-sum[top-1]; //计算区间内元素和 tmp*=a[top]; //计算结果 if(tmp>=ans) { //更新最大值并记录位置 ans=tmp; pos1=top; pos2=i; } } st.push(top); //将最后一次出栈的栈顶元素入栈 a[top]=a[i]; //将其向左向右延伸并更新对应的值 } } printf("%lld ",ans); printf("%d %d ",pos1,pos2-1); } return 0; }
#include<iostream> #include<cstring> #include<stack> #include<cmath> #include<cstdio> using namespace std; stack<int > num; long long a[100005],sum[100005]; int main() { int n; long long ans,tmp,top; int posf,posl; while(~scanf("%d",&n)) { while(!num.empty()) num.pop(); ans=0; scanf("%lld",&a[0]); sum[0]=a[0]; for(int i=1; i<n; i++) { scanf("%lld",&a[i]); sum[i]=sum[i-1]+a[i]; } a[n]=-1; for(int i=0; i<=n; i++) { if(num.empty()||a[i]>=a[num.top()]) num.push(i); else { while(!num.empty()&&a[i]<a[num.top()]) { top=num.top(); num.pop(); tmp=(sum[i-1]-sum[top-1])*a[top]; if(tmp>=ans) { ans=tmp; posf=top+1; posl=i; } } num.push(top); a[top]=a[i]; } } printf("%lld %d %d ",ans,posf,posl); } return 0; }
现将每一个的前缀和求出
对a数组单调递增 ..将其下标加入栈中然后遇到小于的栈顶的 就求区间和(sum[i-1]-sum[top-1])*a[top];
弹出栈顶就这个样子 因为单调递增 所以如果每次弹出的栈顶一定是区间 内最小的a; 别忘记更新栈
将最后一个弹出的栈顶入栈 并且将其值更新为新的最小值
入栈原因感觉就像是 划分了一个区域(看做一个点)/断点(新的起点) 比如1234 1234-1 或者1234 0 12345-1
然后附上大神解析 单调栈 链接