华为OJ【问题描述】 给定一个正整数N代表火车数量，0< N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。 输入: 有多组测试用例，每一组第一行输入一个正整数N（0< N<10），第二行包括N个正整数，范围为1到9。 输出: 输出以字典序排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。 样例输入: 3 1 2 3 样例输出: 1 2 3 1 3 2 2 1 3 2 3 1 3 2 1
解题思路：此题的本质就是给你一个入栈序列，求出其所有出栈序列的情况。根据样例输出，我们可以观察出这可能是一个数组的全排列过程，只是少了部分情况，而那部分情况就是不满足出栈序列的，比如3 1 2，若先出3，则1 2在栈里，此时再出 1 就不满足出栈序列了。所以：当对数组全排列以后，在输出阶段，再判断此排列是否满足出栈序列，即从当前值开始，后序所有的值为降序排列，就符合出栈，否则，不符合。代码如下：
#include <iostream> #include<string> #include<vector> #include<algorithm> #include <fstream> using namespace std; void PrintNum(vector<int>); void Perm(vector<int> &data,int start) { if(start == data.size()-1) { PrintNum(data); return; } for(int i = start;i < data.size();++i) { swap(data[i],data[start]); Perm(data,start+1); swap(data[i],data[start]); } } void PrintNum(vector<int> data) { int size = data.size(); int m_small = 0; bool flag = true; for(int i = 0;i < size;++i) { int curr_small = 0; for(int j = i+1;j < size && flag;++j) { if(data[i] > data[j])//不能只要data[i] > data[j]就更新较小的值，应该判断的是较小值后面的值是否降序，所以只记录当前i中第一个比data[i]小的值 { if(curr_small == 0) //记录当前第一个比data[i]小的值，用于判断后面的值是否是降序，满足出栈要求 m_small = data[j],++curr_small; else { if(data[j] > m_small) //如果之后出现的数比记录的数还大，改变flag flag = false; else //否则记录这个更小的数 m_small = data[j]; } } } } if(flag) { for(int i = 0;i < size;++i) { cout<<data[i]<<" "; } cout<<endl; } } int main() { vector<int> data(3,0); data[0] = 1; data[1] = 2; data[2] = 3; Perm(data,0); }