列车调度——典型的验证栈的出栈合不合法的问题，值得一看

本文主要是介绍列车调度——典型的验证栈的出栈合不合法的问题，值得一看，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

有n列火车按照1,2,3...n的顺序排列，现所有的火车需要掉头，所以需要火车先驶入一个调度站，再开出来。

由于只有一根铁轨，所以要么最前面的一辆火车进去调度站，要么调度栈内最上面一辆火车开出调度栈。

现给定一个出调度站的，顺序，判断是否合理

输入格式

第一行n，第二行1--n的排列

输出格式

如果出站顺序合理，输出“YES”，否则输出“NO”

样例 #1

样例输入 #1

3
3 1 2

样例输出 #1

NO

提示

数据范围：n<=10000;

思路

我原本想的是用暴力枚举来看有没有输入的这种，但后来推出了栈内元素出栈的规律，那就是

出栈序列中的每个数后面的比它小的数，是按递减排列的。

基于此，我们就可以写出一下代码

#include<bits/stdc++.h>
using namespace std;int a[10010],cnt;
int main(){int n;cin>>n;for (int i=0;i<n;i++){cin>>a[i];}for (int i=0;i<n;i++){cnt=a[i];for (int j=i+1;j<n;j++){if (a[i]>a[j]){if (a[j]<cnt){cnt=a[j];}else {cout<<"NO";return 0;}}}}cout<<"YES";return 0;
}

看了这么久，作者也写了这么久，能不能点一个赞，在收藏一下呢？最好的话在点个关注吧

谢谢啦！