实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解析：本题实现上不难，主要在于想明白逻辑。
什么是字典序？就是类似于字典上的目录排序，就比如123的字典序排列出来便是：
123、132、213、231、312、321
如果不了解什么是字典序那么肯定不知道怎么做

对于一个序列，我们需要找到它的尾部最长递减序列，例如序列1,2,3,4,5,6,7,6,5,4,3,2,1
它的这个序列便是7,6,5,4,3,2,1。这一部分在字典序中已经是最大的，因此在下一个排列中，它必然会重新排列为最小的顺序，而对于这个递减序列，便是将它倒转。
此时的序列变为1,2,3,4,5,6,1,2,3,4,5,6,7

对于原序列，最长递减序列之前的数字为6，如果去掉它之前的部分，6,7,6,5,4,3,2,1.
6之后的子序列已经是最大的排列，因此下一个序列必然会交换这个子序列前面的数字6,以构筑一个比原序列大，并在所有可能序列中最小的下一个排序。

为了让这个序列更大，必须将6变为一个更大的数字，所以从6之后的子序列，找到一个比6大且相对最小的数字，对于本例为7，将这两个数字交换，便得到了下一个字典序
1,2,3,4,5,7,1,2,3,4,5,6,6

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()<2) return;
        //寻找数组末尾的最长递减序列
        int i;
        for(i=nums.size()-1;i>0&&nums[i-1]>=nums[i];--i);

        //将该递减序列倒置
        //手写版
        /*int l=0+i;
        int r=nums.size()-1;
        while(l<r){
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            ++l,--r;
        }*/
        //库函数版
        reverse(nums.begin()+i,nums.end());
        //如果i为0，则代表整个数组都是递减的，即目前的数组已经是最大的字典序
        //经过倒转后已经变成最小排列，所以不需要这一步骤

        //手写版
        /*if(i--!=0){
            int j = i;
            //寻找比倒转序列前一个数字大的下一个数字
            while(nums[i]>=nums[j]) ++j;
            //将它们交换
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }*/
        //库函数版
        if(i--!=0){
            auto it = upper_bound(nums.begin() + i, nums.end(), nums[i]);
            swap(nums[i], *it);
        }

        //其实整个功能都可以用自带的库函数一行解决...但毕竟是算法题
        //next_permutation(nums.begin(),nums.end()); 

    }
};