class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k && nums[k - 1] >= nums[k]) 
            k --; // 找出逆序(nums[k-1], nums[k)使得nums[k-1]<nums[k],nums[k] >= nums[k ++++++]

        if (k <= 0) reverse(nums.begin(), nums.end()); //如果是“321”这种情况，直接输出reverse()
        else { //找比nums[k-1]大的最小的数 nums[t-1],找到后交换nums[k-1], nums[t-1]
            int t = k;
            while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
            swap(nums[t - 1], nums[k - 1]);
            reverse(nums.begin() + k, nums.end()); //再将nums[k-1]后面的所有数逆序输出（升序输出）
        }
    }
};