学步园

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3

1,1,5 → 1,5,1

      求下一个大于当前排列的排列。即从后向前找到第一个num[i]>num[i-1]的位置，这里用从num[i]..到num.end()之间的大于num[i-1]的最小的元素num[j]与num[i-1]互换，再把num[i]到num.end()之间的元素按从小到大排列。即为大于当前排列的最小的排列。

      这里对num[i]...num.end()的从小到大调整之所以可以用reverse()，是因为num[i]<num[i-1]是第一个满足的位置，num[i]到num.end()之间肯定是从大到小有序排列，所以可以用reverse()反序为从小到大排列

class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(num.size()==0||num.size()==1)return;
        int i,j,curNum,curJ;
        for(i=num.size()-1;i>=1;i--){
            if(num[i]>num[i-1])break;
        }
        if(i==0)reverse(num.begin(),num.end());
        else{
            for(j=i;j<num.size();j++){
                if(num[j]<=num[i-1])break;
            }
            j--;
            swap(num[j],num[i-1]);
            reverse(num.begin()+i,num.end());
        }
        return;
    }
};