题目描述

给定一个 32 位正整数 n，你需要找到最小的 32 位整数，其与 n 中存在的位数完全相同，并且其值大于 n。如果不存在这样的 32 位正整数，则返回-1。

样例

输入: 12
输出: 21

输入: 21
输出: -1

算法

(贪心) $O(\log n)$

1. 我们把 n 看成一个字符串，这道题相当于求字符串的下一个排列。
2. 有关题解可以参考 LeetCode 31 题解 ，只不过这里的字符串是低位在低地址。

时间复杂度

• 相当于按位处理数字，故时间复杂度为 $O(\log n)$。

空间复杂度

• 需要额外的数组存储数字串，故空间复杂度为 $O(\log n)$。

C++ 代码

class Solution {
public:
    int nextGreaterElement(int n) {
        string s;
        while (n) {
            s += (char) (n % 10 + '0');
            n /= 10;
        }
        int l = s.length();
        int j = -1;
        for (int i = 1; i < l; i++)
            if (s[i] < s[i - 1]) {
                j = i;
                break;
            }

        if (j == -1)
            return -1;

        for (int i = 0; i < j; i++)
            if (s[i] > s[j]) {
                swap(s[i], s[j]);
                break;
            }

        reverse(s.begin(), s.begin() + j);

        long long ans = 0;
        for (int i = l - 1; i >= 0; i--)
            ans = ans * 10 + s[i] - '0';

        if (ans >= 1ll << 31)
            ans = -1;
        return ans;
    }
};