题目描述

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

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

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

样例

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

算法1

按stl next_permutation的原理来

例如：
12345 下一个排列是12354，找到第一个从右往左的a[k+1] < a[k]的数4,再和k+1到n-1第一个小于4的数往左一个数交换，对k+1到n-1逆序得到12354

                   /\
找到这个数    --->  \\<---以及这个数，交换它们，再由山顶到右半山脚逆序就是答案
                      \

C++ 代码

class Solution {
public:
    void nextPermutation(vector<int>& q) {
        if(q.size()==1)return;
        if(q[0] > q[1] || q[0] == q[1])
        {
            bool flag = true,m = true;      
            for(int i = 0 ; i+1 < q.size();i++)
            {
                if(q[i] != q[i+1])m = false;
                if(q[i] < q[i+1])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
            {
                reverse(q.begin(),q.end());
                return;
            }
            if(m)return;
        }
        int k = q.size()-2;
        while(q[k] >= q[k+1])k--;
        int t = q.size()-1;
        while(q[t] <= q[k] && t > k) t--;
        swap(q[k],q[t]);
        reverse(q.begin()+k+1,q.end());
    }
};