力扣hot100：31. 下一个排列

LeetCode：31. 下一个排列

字典序的大小排序：

• 从前往后对比，如果先出现更小字符的，字典序更小，如果有个字符串结束了，则它更小。
• string s = "112233"和string t = "1122334"，s更小

根据字典序排序说法，我们想找到尽可能小的比当前字典序大的字符串，我们就要尽可能的使得字典序大的出现在更右边。

我们考虑极端情况，如"1122334"，比它更大一点的将是"1122343"，我们会发现，我们只需要将右边较大的一个数与前面较小的一个数交换就能变得更大，不过为了更小我们需要将交换后的后面部分从小到大排序。

• "14321"，从右往前看，最右边的1走到4都是升序，也就是这一段不可能可以交换变得更大，同理，只要从右边开始看，一直是升序的段，就不可能可以交换变得更大，而如果出现非升序，也就是最左边的1，那就必然可以交换了，因为一定有右边存在一个数比这个数大！
• 当然我们想要最小的更大的数跟最左边的1交换，我们就需要找到2。

算法思路：
124 2 98765432

1. 从右往左，找到一个断层的第一个数（如果没有，那么整个降序就是答案，再给出的例子里是空出来的2）
2. 在这个断层的数右边找一个比它大但在右边最小的数，与其交换。（交换后右边的数还是顺序排列的，这个更大数是右边的3,交换后变为124398765422）
3. 反转右边的数（注意右边的数一定是按顺序排列的，因为我们按1.的方式进行查找的，反转后变为124322456789，这保证了更大，但是是更大中的最小的那一个。）

时间复杂度：$O(n)$
空间复杂度：$O(1)$

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