L2-032 彩虹瓶

题目 L2-032 彩虹瓶

思路分析

问题提炼出来

实际是问 给定入栈顺序 能不能以123456……n的顺序出栈 （加一个条件栈深不得超过m）

代码实现

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int ,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

int n,m,k;

bool check(vector<int> pushV,vector<int> popV){

	stack<int> stk;

	int i=0;

	for(auto x:pushV){

		if(x==popV[i]){

			i++;

			while(!stk.empty() && stk.top()==popV[i]){

				stk.pop();

				i++;

			}

		}else{

			stk.push(x);

			if(stk.size()>m){

				return false;

			}

		}

	}

	return stk.empty();

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>m>>k;

	vector<int> popV(n);

	for(int i=0;i<n;i++){

		popV[i]=i+1;

	}

	while(k--){

		vector<int> pushV(n);

		for(int i=0;i<n;i++){

			cin>>pushV[i];

		}

		if(check(pushV,popV)){

			cout<<"YES"<<endl;

		}else{

			cout<<"NO"<<endl;

		}

	}

	return 0;

}

同类题型

视频讲解

⬅️ L2-031 深入虎穴 🏠 00-天梯赛 ➡️ L2-033 简单计算器