31. Next Permutation

题目链接

https://leetcode.com/problems/next-permutation/

解题思路

拿一个例子来说明，如下：

7, 5, 1, 2, 6, 3, 0

1. 从后往前找第一个相邻两个元素后一个元素大于前一个元素，也就是2和6
2. 在2后面也是从右往前周第一个大于2的数，也就是3
3. 交换2和3

7, 5, 1, 3, 6, 2, 0

4. 对3后面的数转置一下，就可以得到答案

7, 5, 1, 3, 0, 2, 6

在第1步找到的2和6，2之后的数肯定是降排，在第2和3步之后，3后面的数仍然满足降排性质，所有在对3后面的数进行转置得到一个升排就是答案。

代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() < 2) {
            return;
        }

        //从后往前找第一个符合nums[i] > nums[i - 1]
        for (int i = nums.size() - 1; i > 0 ; i--) {
            if (nums[i] > nums[i - 1]) {
                //在nums[i - 1]之后找比nums[i - 1]大且最小的数进行交换
                for (int k = nums.size() - 1; k >= i ; --k) {
                    if (nums[k] > nums[i - 1]) {
                        swap(nums[i - 1], nums[k]);
                        break;
                    }
                }

                //转置下
                reverse(nums.begin() + i, nums.end());
                return;
            }
        }
        reverse(nums.begin(), nums.end());
    }
};