【556. 下一个更大元素 III】

来源：力扣（LeetCode）

描述：

给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。

注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。

示例 1：

输入：n = 12
输出：21

示例 2：

输入：n = 21
输出：-1

提示：

1 <= n <= 2³¹ - 1

方法一：下一个排列

把 n 转换成字符串（字符数组），那么本题实际上是在求字符数组的 下一个排列，当不存在下一个排列时返回 −1。

代码：

class Solution {
    
public:
    int nextGreaterElement(int n) {
    
        auto nums = to_string(n);
        int i = (int) nums.length() - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
    
            i--;
        }
        if (i < 0) {
    
            return -1;
        }

        int j = nums.size() - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
    
            j--;
        }
        swap(nums[i], nums[j]);
        reverse(nums.begin() + i + 1, nums.end());
        long ans = stol(nums);
        return ans > INT_MAX ? -1 : ans;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了57.91%的用户
复杂度分析
时间复杂度： O(logn)。
空间复杂度：O O(logn)。

方法二：数学

不转换成字符数组，如何用 O(1) 空间复杂度解决此题？

如果还要求不使用 64 位整数呢？

类似方法一，我们从 n 开始，不断比较其最低位数字和次低位数字的大小，如果次低位数字不低于最低位数字，则移除最低位数字，继续循环。循环结束后的 n 就对应着方法一的下标 i，即 nums 的前 i + 1 个字符。

对于方法一中下标 j 的计算也是同理。

代码：

class Solution {
    
public:
    int nextGreaterElement(int n) {
    
        int x = n, cnt = 1;
        for (; x >= 10 && x / 10 % 10 >= x % 10; x /= 10) {
    
            ++cnt;
        }
        x /= 10;
        if (x == 0) {
    
            return -1;
        }

        int targetDigit = x % 10;
        int x2 = n, cnt2 = 0;
        for (; x2 % 10 <= targetDigit; x2 /= 10) {
    
            ++cnt2;
        }
        x += x2 % 10 - targetDigit; // 把 x2 % 10 换到 targetDigit 上

        for (int i = 0; i < cnt; ++i, n /= 10) {
     // 反转 n 末尾的 cnt 个数字拼到 x 后
            int d = i != cnt2 ? n % 10 : targetDigit;
            if (x > INT_MAX / 10 || x == INT_MAX / 10 && d > 7) {
    
                return -1;
            }
            x = x * 10 + d;
        }
        return x;
    }
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了94.76%的用户
复杂度分析
时间复杂度： O(logn)。
空间复杂度： O(1)。我们只需要常数的空间保存若干变量。
author：LeetCode-Solution