leetcode-31. 下一个排列

leetcode-31. 下一个排列

1. 从后向前找，找非降序排列的第一个位置, nums[k-1] < nums[k]
2. 从后向前找，找

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k > 0) 
        {
            if (nums[k-1] < nums[k]) break;
            else k--;
        }
        // 如果序列是 纯递减序列，就翻转一下
        if (k <= 0) reverse(nums.begin(), nums.end());
        else {
            // nums[k-1] 和 k 是第一个 升序的，要在 k 后面找到比 nums[k-1] 大的最小的数
            int t = nums.size() - 1;
            // 从后向前找 t
            while (t > 0 && nums[t] <= nums[k - 1]) t--;

            swap(nums[k-1], nums[t]); // 把2个数交换
            sort(nums.begin() + k, nums.end()); // 翻转 nums[k] 后面的所有数，把降序变为升序
        }
    }
};