栈

一般应用

P4387 【深基15.习9】验证栈序列 - 洛谷

多组数据记得清空栈

#include <bits/stdc++.h>
using ll=long long;
using namespace std;int main() {int t; cin>>t;while(t--){int n;cin>>n;int a[n],b[n];for(int i=0;i<n;++i) cin>>a[i];for(int i=0;i<n;++i) cin>>b[i];stack<int> s;	int ai=0,bi=0;while(ai<n){s.push(a[ai]);while(!s.empty()&&s.top()==b[bi]){s.pop();bi++;}ai++;}if(bi==n) cout<<"Yes\n";else cout<<"No\n";} return 0;
}

735. 小行星碰撞 - 力扣（LeetCode）

class Solution {
public:vector<int> asteroidCollision(vector<int>& asteroids) {vector<int> s;int n=asteroids.size();for(int i=0;i<n;i++){if(asteroids[i]>0||s.size()==0){s.push_back(asteroids[i]);}else{while(s.size()!=0&&s.back()>0&&s.back()<-asteroids[i]){s.pop_back();}if(s.size()==0||s.back()<0){s.push_back(asteroids[i]);} else if(s.back()==-asteroids[i]){s.pop_back();}}}return s;}
};

单调栈

栈中的元素是严格单调递增或者递减的，也就是说：从栈底到栈顶，元素的值逐渐增大或者减小。

要描述清楚如何增大：从底向顶递增、从顶向底递增

• 解决问题：

向左/右找第一个比自身大/小的数。

元素间大小判断：对于当前遍历到的数，栈顶为答案。

1.向左找第一个比自己大的数。左—>右 底到顶递减栈

2.向左找第一个比自己小的数。左—>右 底到顶递增栈

3.向右找第一个比自己大的数。右—>左 底到顶递减栈

4.向右找第一个比自己小的数。右—>左 底到顶递增栈

这个方法更简单

• 模板

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=1e3+5;int n;
int a[N];
stack<int> s;
int ans[N];//ans[i]就是a[i]左边第一个比a[i]大的数//向左找第一个比自己大的数。左--->右 底到顶递减栈int main() {cin>>n;for(int i=1;i<=n;++i){cin>>a[i];}   	for(int i=1;i<=n;++i){//栈非空并且当前栈顶小于a[i]  连续出栈while(!s.empty()&&s.top()<=a[i]){s.pop();} //栈可能为空if(s.empty()){ans[i]=-1;} else{ans[i]=s.top();}s.push(a[i]);//入栈时记录答案 }for(int i=1;i<=n;++i){cout<<ans[i]<<" ";}return 0;
}

元素间大小判断：对于栈顶，当前遍历到的数为答案。

1.向左找第一个比自己大的数。右—>左 底到顶递减栈

2.向左找第一个比自己小的数。右—>左 底到顶递增栈

3.向右找第一个比自己大的数。左—>右底到顶递减栈

4.向右找第一个比自己小的数。左—>右底到顶递增栈

这个方法稍微复杂

• 模板

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=1e3+5;int n;
int a[N];
stack<int> s;
int ans[N];//ans[i]就是a[i]左边第一个比a[i]大的数//向左找第一个比自己大的数。右--->左 底到顶递减栈int main() {cin>>n;for(int i=1;i<=n;++i){cin>>a[i];}   	//下标入栈 for(int i=n;i>=1;--i){//栈非空并且当前栈顶小于a[i] while(!s.empty()&&a[s.top()]<a[i]){ans[s.top()]=a[i];s.pop();} s.push(i); }//剩下的是左边无比他大的数 while(!s.empty()){ans[s.top()]=-1;s.pop();} for(int i=1;i<=n;++i){cout<<ans[i]<<" ";}return 0;
}

P5788 【模板】单调栈 - 洛谷

#include <bits/stdc++.h>
using ll=long long;
using namespace std;
const int N=1e7+5;int n;
int a[N];
stack<int> s;
int ans[N];int main() {cin>>n;for(int i=1;i<=n;++i){cin>>a[i];}   	for(int i=n;i>=1;--i){//从右往左while(!s.empty()&&a[s.top()]<=a[i]){//<=!s.pop();}if(s.empty()){s.push(i);ans[i]=0;}else{ans[i]=s.top();s.push(i); } } for(int i=1;i<=n;++i){cout<<ans[i]<<" ";}return 0;
}

42. 接雨水 - 力扣（LeetCode）

class Solution {
public:int trap(vector<int>& height) {int n=height.size();stack<int> s;int ans=0;for(int i=0;i<n;++i){while(!s.empty()&&height[s.top()]<height[i]){int b=s.top();//凹槽底部s.pop();if(!s.empty()){//新的栈顶是凹槽的左边柱子int h=min(height[i],height[s.top()])-height[b];//水量的高度int w=i-s.top()-1;//宽度ans+=w*h;}}s.push(i);//入栈} return ans;}
};