题解64 | 兄弟分了安慰下一个更好#下一个更大的数(三)#

类似字符串-下一个排列 链接：https://www.nowcoder.com/practice/50b0b87e50be4944b34cb0f2ce618197

#include <climits>
#include <string>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    void nextPermutation(string &nums){
        int len = nums.size();
        for (int i = len - 1; i >= 0; i--) {
            for (int j = len - 1; j > i; j--) {
                if (nums[i] < nums[j]) {
                    swap(nums[j],nums[i]);//从低位去寻找，然后交换
                    reverse(nums.begin()+i+1,nums.end());
                    return ;
                }
            }
        }
    }
    int nextGreaterElement(int n) {
        // write code here
        string s = to_string(n);
        nextPermutation(s);
        int ans = stoi(s);
        return ans > INT_MAX ? -1 : ans > n ? ans : -1;
    }
};

算法基本思想：（手搓一个nextPermutation函数）

1. 将输入的整数n转换为字符串s。

2. 调用nextPermutation函数，对字符串s进行下一个排列的操作，得到下一个排列的字符串。

2.5.当调用nextPermutation函数时，会将一个字符串作为参数传入函数中。

1. 首先获取字符串的长度len。

2. 从字符串的末尾开始向前遍历，找到第一个满足nums[i] < nums[j]的位置i，其中i之后的部分是降序排列的。

3. 然后再次从末尾开始向前遍历，找到第一个大于nums[i]的位置j。

4. 交换nums[i]和nums[j]。

5. 将位置i之后的部分进行翻转，使其变为升序排列。

6. 返回得到的下一个排列字符串。

3. 将下一个排列的字符串转换为整数ans。

4. 如果ans大于INT_MAX，返回-1；如果ans大于n，返回ans，否则返回-1。

时间复杂度：

O(n^2)，其中n为输入整数的位数。nextPermutation函数中使用了嵌套循环，时间复杂度为O(n^2)。

空间复杂度：

O(n)，需要额外的空间存储字符串s和下一个排列的字符串。