LC 556. 下一个更大元素 III

题目描述

这是 LeetCode 上的 556. 下一个更大元素 III ，难度为 中等。

给你一个正整数 $n$，请你找出符合条件的最小整数，其由重新排列 $n$ 中存在的每位数字组成，并且其值大于 $n$。

如果不存在这样的正整数，则返回 $-1$ 。

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

示例 1：

1
2
3
输入：n = 12

输出：21

示例 2：
1
2
3
输入：n = 21

输出：-1

提示：

  • $1 <= n <= 2^{31} - 1$

模拟

根据题意，只有给定数字 $x$ 本身从高位到低位是「非严格降序」时，我们无法找到一个合法值。

首先，我们可以先对 $x$ 诸位取出，存成 nums 数组（数组的首位元素为原数 $x$ 的最低位）。

然后尝试找到第一个能够交换的位置 idx（若无法找到，说明不存在合法值，返回 $-1$），即从 $nums[0]$（原始 $x$ 的最低位）开始找，找到第一个「降序」的位置 idx，然后从 $[0, idx)$ 范围内找一个比 $nums[idx]$ 要大的最小数与其进行互换，也是从 $nums[0]$ 开始找，找到第一个满足比 $nums[idx]$ 大的数。

当互换完成后，此时比 $x$ 要大这一目标已由第 idx 位所保证（后续的排序应该按照从小到大放置），同时互换结束后的 $[0, idx)$ 仍然满足「非严格升序」特性，因此我们可以对其运用「双指针」进行翻转。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int nextGreaterElement(int x) {
        List<Integer> nums = new ArrayList<>();
        while (x != 0) {
            nums.add(x % 10);
            x /= 10;
        }
        int n = nums.size(), idx = -1;
        for (int i = 0; i < n - 1 && idx == -1; i++) {
            if (nums.get(i + 1) < nums.get(i)) idx = i + 1;
        }
        if (idx == -1) return -1;
        for (int i = 0; i < idx; i++) {
            if (nums.get(i) > nums.get(idx)) {
                swap(nums, i, idx);
                break;
            }
        }
        for (int l = 0, r = idx - 1; l < r; l++, r--) swap(nums, l, r);
        long ans = 0;
        for (int i = n - 1; i >= 0; i--) ans = ans * 10 + nums.get(i);
        return ans > Integer.MAX_VALUE ? -1 : (int)ans;
    }
    void swap(List<Integer> nums, int a, int b) {
        int c = nums.get(a);
        nums.set(a, nums.get(b));
        nums.set(b, c);
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int nextGreaterElement(int x) {
        vector<int> nums;
        while (x != 0) {
            nums.push_back(x % 10);
            x /= 10;
        }
        int n = nums.size(), idx = -1;
        for (int i = 0; i < n - 1 && idx == -1; i++) {
            if (nums[i + 1] < nums[i]) idx = i + 1;
        }
        if (idx == -1) return -1;
        for (int i = 0; i < idx; i++) {
            if (nums[i] > nums[idx]) {
                swap(nums[i], nums[idx]);
                break;
            }
        }
        reverse(nums.begin(), nums.begin() + idx);
        long long ans = 0;
        for (int i = n - 1; i >= 0; i--) ans = ans * 10 + nums[i];
        return ans > INT_MAX ? -1 : static_cast<int>(ans);
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def nextGreaterElement(self, x: int) -> int:
        nums = []
        while x != 0:
            nums.append(x % 10)
            x //= 10
        n, idx = len(nums), -1
        for i in range(n - 1):
            if nums[i + 1] < nums[i]:
                idx = i + 1
                break
        if idx == -1: return -1
        for i in range(idx):
            if nums[i] > nums[idx]:
                nums[i], nums[idx] = nums[idx], nums[i]
                break
        l, r = 0, idx - 1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l, r = l + 1, r - 1
        ans = 0
        for num in nums[::-1]: ans = ans * 10 + num
        return -1 if ans > 2**31 - 1 else ans

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function nextGreaterElement(x: number): number {
    const nums = [];
    while (x !== 0) {
        nums.push(x % 10);
        x = Math.floor(x / 10);
    }
    const n = nums.length;
    let idx = -1;
    for (let i = 0; i < n - 1 && idx == -1; i++) {
        if (nums[i + 1] < nums[i]) idx = i + 1;
    }
    if (idx == -1) return -1;
    for (let i = 0; i < idx; i++) {
        if (nums[i] > nums[idx]) {
            [nums[i], nums[idx]] = [nums[idx], nums[i]];
            break;
        }
    }
    for (let l = 0, r = idx - 1; l < r; l++, r--) [nums[l], nums[r]] = [nums[r], nums[l]];
    let ans = 0;
    for (let i = n - 1; i >= 0; i--) ans = ans * 10 + nums[i];
    return ans > 2**31 - 1 ? -1 : ans;
};

  • 时间复杂度：$O(\log{n})$
  • 空间复杂度：$O(\log{n})$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.556 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。