栈
一般应用
多组数据记得清空栈
#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;
}
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;
}
#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;
}
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;
}
};