我的思路：火车站可看做stack，对于每节车厢，有两种选择，入栈或直接前进。那么要判断顺序是否合法，只需要这样：

设置一个指向判断序列的指针，对于1-n的每个数字，如果该数字小于指针指向的数字，那么push。

如果相等，依次判断指针后面的数字是否比该数字小，如果小那么必定在栈顶，在的话就pop，不在的话就是不可能的序列。

version 1(40ms):

#include
    
     using namespace std;const int maxn = 1000 + 5;int main(){    // freopen("data.in","r",stdin);    // freopen("data.out","w",stdout);    int n,a[maxn];    while(scanf("%d",&n) && n){        while(scanf("%d",&a[0]) && a[0]){            stack
     
      s;            int mark = 1;            for(int i = 1;i < n;i++) scanf("%d",&a[i]);            int j = 0;            for(int i = 1;i <= n && mark;i++){                if(i < a[j]) s.push(i);                else{                    j++;                    while(j < n && a[j] < i){                        if(!s.size() || a[j] != s.top()){                            mark = 0;                            break;                        }                        else{                            s.pop();                            j++;                        }                    }                }            }            printf("%s\n",mark ? "Yes" : "No");        }        putchar('\n');    }    return 0;}
     
    

version 2（书上版本，30ms）：

#include
    
     using namespace std;const int maxn = 1000 + 5;int main(){    // freopen("data.in","r",stdin);    // freopen("data.out","w",stdout);    int n,a[maxn];    while(scanf("%d",&n) && n){        while(scanf("%d",&a[0]) && a[0]){            int mark = 1;            for(int i = 1;i < n;i++) scanf("%d",&a[i]);            int i = 1,j = 0;            stack
     
      s;            while(j < n){                if(i == a[j]){ i++; j++; }                else if(s.size() && s.top() == a[j]){ s.pop(); j++; }                else if(i <= n) s.push(i++);                else{ mark = 0; break; }            }            printf("%s\n",mark ? "Yes" : "No");        }        putchar('\n');    }    return 0;}