一本通3.1栈黄色线：2020.3.9
熟悉的图又回来了，其实这一次就一道题，还特简单的一道
1357：车厢调度·
因为这次就一道题，我代码就写得细一点，前面的代码解释太少了，我把思路也写写
思路一：
模拟算法，因为a[i]出栈前，若他在B轨上，则1~a[i]-1这些数都得在栈中或出栈，所以我就叫之前的全进栈，至C中;而a[i]若在栈中，压在前面的必须出去，“放空”通道，让a[i]出栈。详见代码解释。
#include <bits/stdc++.h>
using namespace std;
int a[1050],n,nown=1;
//nown是当前从B轨入栈的序号，当前进入到第几个了
//因为我是有序进栈，那就是最后进栈的编号
stack<int> s;//栈
//stack（栈）可用数组代替，但我更喜欢用stack，操作起来方便，也好用
int main()
{
cin>>n;
for(int i=1; i<=n; i++) cin>>a[i];//输入
for(int i=1; i<=n; i++)
{
while(nown<=a[i])//若在B轨上
s.push(nown++);//把前面的压入
if(s.top()==a[i]) s.pop();//如果栈顶是当前的要出栈车厢号，那么就出栈。
else//不然就说明无法达到目标，输出“NO”
{
cout<<"NO\n";//一定要大写哦
return 0;
}
}
cout<<"YES\n";//大写哦
return 0;
}
思路二：按题目说的方法
//
从第一个数字开始扫描，a[i]表示当前出栈的数字，如果有比a[i]大的数字还在栈中，那么就产生矛盾，输出“NO”；否则，标记当前数字a[i]为栈后状态，那么[1, a[i]-1]这些数字如果还没出栈，标记为栈中状态。具体我们可以用0表示为确定状态，1表示栈中状态，2表示栈后状态。 ——ybt一本通（🐏鼻涕）官方网站
//
那就简单了，代码嘛，直接上
#include <bits/stdc++.h>
using namespace std;
int sta[1050],a[1050],n,top,nown[1050];
int main()
{
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
if(nown[a[i]]==1)//在栈中
if(sta[top--]==a[i])//最上面
nown[a[i]]=2;//推到栈后
else
{
cout<<"NO"<<endl;
return 0;//输出不可能
}
for(int j=1; j<a[i]; j++)//前面未入栈的
{
if(nown[j]==0)
{
nown[j]=1;
sta[++top]=j;
}//入栈
}
nown[a[i]]=2;//a[i]出栈（栈后）
}
cout<<"YES"<<endl;
return 0;
}
这种方法有点烦，不过也是一种好的方法，能过就行。
总结一下，两种方法，各有各的好处，当然，网上给的代码全是第一种，其实第二种也不错啦，看个人选择。有提示，顺着它最好，但用自己的方法，也不是说差。有兴趣的，可以像我一样，两种思路都码，可以练练手。
