题意转化

条件1.求一个比原序列字典序更大的序列
条件2.并且字典序变大的增量要尽量的小

思考方式

⭐1 既然要比原序列大，那么必然存在第一个不一样的位置i。不难想到i越往后越好，并且这个num[i]能变大才行，并且变大后的数还要尽可能的小。
⭐2 为了寻找i，我们就从后往前找，找到第一个“可以变大的数”，也就是它的后面存在比它大的数，那么这个位置就是i。没有比这个位置更优的位置了，然后为了尽量压低新的num[i]，再遍历一下，找到它的后面比它大的的数中最小的那个，交换他们的值。
⭐3 既然i确定了，也就是说新序列的0~i+1位置上的数我们都确定了，而且我们能确保条件1，为了达到条件2，把剩下的数排个序就行了。可以这么想，反正我们已经比原序列大了，这么剩下的数你想怎么折腾就那么折腾，那当然是怎么小怎么来。

代码 时空复杂度O(nlogn)/O(1)

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