51. Previous Permutation

image.png
image.png
https://www.geeksforgeeks.org/lexicographically-previous-permutation-in-c/
类似于后一个组合数
（1）从后往前找，找到第一个a[i] > a[i + 1];
(2) 在从后往前找，找第一个是a[j] < a[i];
(3)交换a[i] 与 a[j], 将a[i+1] 到最后， 逆序；

class Solution {
public:
    /*
     * @param nums: A list of integers
     * @return: A list of integers that's previous permuation
     */
    vector<int> previousPermuation(vector<int> &nums) {
        // write your code here
        if(nums.size() == 0 || nums.size() == 1) return nums;
        int i = nums.size() - 2;
        int j = nums.size() - 1;
        while(i >= 0 && nums[i] <= nums[i+1]) i--;
        if(i >= 0){
            while(nums[j] >= nums[i]) j--;
            swap(nums[i], nums[j]);
        }
        reverse(nums.begin() + i + 1, nums.end());
        return nums;
    }
};