【华为机试题】【栈】【全排列】火车进站

链接：https://www.nowcoder.com/questionTerminal/97ba57c35e9f4749826dc3befaeae109
来源：牛客网

火车进站

热度指数：6730 时间限制：1秒空间限制：32768K

算法知识视频讲解

给定一个正整数N代表火车数量，0<N<10，接下来输入火车入站的序列，一共N辆火车，每辆火车以数字1-9编号。要求以字典序排序输出火车出站的序列号。

输入描述:

有多组测试用例，每一组第一行输入一个正整数N（0<N<10），第二行包括N个正整数，范围为1到9

输出描述:

输出以字典序从小到大排序的火车出站序列号，每个编号以空格隔开，每个输出序列换行，具体见sample。

示例1

输入
3
1 2 3
输出
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1

问题分析:

1.全排列

2.根据栈后进先出的特点筛去原始进站顺序无法出栈得到的排列

方法要点:

std::next_permutation() 排序函数的使用
default (1)
template <class BidirectionalIterator>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last);
custom (2)
template <class BidirectionalIterator, class Compare>
  bool next_permutation (BidirectionalIterator first,
                         BidirectionalIterator last, Compare comp);

default (1)	`template <class BidirectionalIterator> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);`
custom (2)	`template <class BidirectionalIterator, class Compare> bool next_permutation (BidirectionalIterator first, BidirectionalIterator last, Compare comp);`

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

//is_order函数用来判断当前排序即v1数组是否可以通过数组v压栈得出
bool is_order(vector<int> &v, vector<int> &v1, int n)
{
	if (v.size() == 0 || v1.size() == 0 || n <= 0)
		return false;
	stack<int> s;
	int j = 0;
	for (size_t i = 0; i < v.size(); i++)
	{
		s.push(v[i]);
		while (j < n && s.size() != 0 && v1[j] == s.top())
		{
			s.pop();
			j++;
		}
	}
	return s.empty();
}
int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> v(n),v1(n);
		for (int i = 0; i < n;i++)
			cin >> v[i];
		//把输入的数据数组复制一份到v1
		v1.assign(v.begin(),v.end());
		//对v1进行排序 ----------由题目输出要以字典序排序输出可知
		sort(v1.begin(), v1.end());
		do
		{
			if (is_order(v, v1, n))
			{
				for (auto e : v1)
					cout << e << " ";
				cout << endl;
			}
		} while (next_permutation(v1.begin(), v1.end()));
	}
	return 0;
}