31.下一个排列

方法：两遍扫描

举例：
4 5 2 6 3 1排列中较小数为2，较大数为3，交换两者得：4 5 3 6 2 1，将[i+1,n)区间改成升序：得下一个排列： 4 5 3 1 2 6。
若第一步找不到较小数，即当前排列为最大排列，直接进行第3步获得下一个排列，即最小排列。

class Solution{
public:
	void nextPermutation(vector<int>& nums){
		int i=nums.size()-2;
		while(i>0&&nums[i]>=nums[i+1]){
			i--;
		}
		if(i>=0){
			int j=nums.size()-1;
			while(j>=0&&nums[i]>=nums[j]){
				j--;
			}
			swap(nums[i],nums[j]);
		}
		reverse(nums.begin()+i+1,nums.end());
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17