共计 1451 个字符，预计需要花费 4 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 556. 下一个更大元素 III，难度为 中等 。
Tag :「模仿」、「双指针」
给你一个正整数 $n$，请你找出符合条件的最小整数，其由重新排列 $n$ 中存在的每位数字组成，并且其值大于 $n$。如果不存在这样的正整数，则返回 $-1$。
留神，返回的整数该当是一个 $32$ 位整数，如果存在满足题意的答案，但不是 $32$ 位整数，同样返回 $-1$。
示例 1：
输出：n = 12
输入：21示例 2：
输出：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)$ 依然满足「非严格升序」个性，因而咱们能够对其使用「双指针」进行翻转。
代码：
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);
}
}- 工夫复杂度：$O(\log{n})$
- 空间复杂度：$O(\log{n})$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.556 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由 mdnice 多平台公布
