556. 下一个更大元素 III
题目描述
输入一个正整数 n。把 n 的各位数字重新排列，可以得到若干个整数，每个数字都必须恰好用一次。
在这些排列结果中，找出严格大于 n 的最小那个并返回。
如果不存在比 n 大的排列，返回 -1。如果答案存在但超出 32 位有符号整数的范围（大于 2^31 - 1），同样返回 -1。
示例 1
输入：n = 12 输出：21
解释：12 的数字能排成 21，它是唯一更大的排列。
示例 2
输入：n = 21 输出：-1
解释：21 已经是这两个数字能组成的最大值，所以返回 -1。
数据范围
1 <= n <= 2^31 - 1
解题思路
这就是“下一个排列”。第一步从右往左找第一个满足 d[i] < d[i+1] 的位置 i：i 右边是一段非递增的尾巴，它本身已是最大排列，只能动 d[i]。找不到 i 说明整个数已是最大排列，返回 -1。第二步在尾巴里从右往左找第一个比 d[i] 大的 d[j]，它就是尾巴里刚好大于 d[i] 的最小数字，交换两者。第三步交换后尾巴仍是非递增的，用左右双指针把它反转成升序，得到最小的尾巴。最后检查是否超过 2^31 - 1。
为什么正确
第一步中，d[i+1..] 始终是非递增的；交换 d[i] 和 d[j] 后这个性质仍然保持，所以反转就等于升序排序。
复杂度分析
时间 O(L)，L 是位数（最多 10）；额外空间 O(L)。
易错点
两处比较都要带等号（d[i] >= d[i+1]、d[j] <= d[i]），否则遇到重复数字会出错；不要忘记结果可能超过 2^31 - 1，比如 n = 2147483476 的下一个排列 2147483647 合法，而 1999999999 的下一个排列 9199999999 越界。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def nextGreaterElement(self, n: int) -> int:
d = list(str(n))
i = len(d) - 2
while i >= 0 and d[i] >= d[i + 1]:
i -= 1
if i < 0:
return -1
j = len(d) - 1
while d[j] <= d[i]:
j -= 1
d[i], d[j] = d[j], d[i]
lo, hi = i + 1, len(d) - 1
while lo < hi:
d[lo], d[hi] = d[hi], d[lo]
lo += 1
hi -= 1
ans = int(''.join(d))
return ans if ans < 2 ** 31 else -1class Solution {
public int nextGreaterElement(int n) {
char[] d = String.valueOf(n).toCharArray();
int i = d.length - 2;
while (i >= 0 && d[i] >= d[i + 1]) {
i--;
}
if (i < 0) {
return -1;
}
int j = d.length - 1;
while (d[j] <= d[i]) {
j--;
}
char c = d[i]; d[i] = d[j]; d[j] = c;
int lo = i + 1, hi = d.length - 1;
while (lo < hi) {
c = d[lo]; d[lo] = d[hi]; d[hi] = c;
lo++;
hi--;
}
long ans = Long.parseLong(new String(d));
return ans < (1L << 31) ? (int) ans : -1;
}
}class Solution {
public:
int nextGreaterElement(int n) {
string d = to_string(n);
int i = (int)d.size() - 2;
while (i >= 0 && d[i] >= d[i + 1]) {
i--;
}
if (i < 0) {
return -1;
}
int j = (int)d.size() - 1;
while (d[j] <= d[i]) {
j--;
}
swap(d[i], d[j]);
int lo = i + 1, hi = (int)d.size() - 1;
while (lo < hi) {
swap(d[lo], d[hi]);
lo++;
hi--;
}
long long ans = stoll(d);
return ans < (1LL << 31) ? (int)ans : -1;
}
};func nextGreaterElement(n int) int {
d := []byte(strconv.Itoa(n))
i := len(d) - 2
for i >= 0 && d[i] >= d[i+1] {
i--
}
if i < 0 {
return -1
}
j := len(d) - 1
for d[j] <= d[i] {
j--
}
d[i], d[j] = d[j], d[i]
lo, hi := i+1, len(d)-1
for lo < hi {
d[lo], d[hi] = d[hi], d[lo]
lo++
hi--
}
ans, _ := strconv.ParseInt(string(d), 10, 64)
if ans < 1<<31 {
return int(ans)
}
return -1
}var nextGreaterElement = function(n) {
const d = String(n).split('');
let i = d.length - 2;
while (i >= 0 && d[i] >= d[i + 1]) {
i--;
}
if (i < 0) {
return -1;
}
let j = d.length - 1;
while (d[j] <= d[i]) {
j--;
}
[d[i], d[j]] = [d[j], d[i]];
let lo = i + 1, hi = d.length - 1;
while (lo < hi) {
[d[lo], d[hi]] = [d[hi], d[lo]];
lo++;
hi--;
}
const ans = Number(d.join(''));
return ans < 2 ** 31 ? ans : -1;
};function nextGreaterElement(n: number): number {
const d = String(n).split('');
let i = d.length - 2;
while (i >= 0 && d[i] >= d[i + 1]) {
i--;
}
if (i < 0) {
return -1;
}
let j = d.length - 1;
while (d[j] <= d[i]) {
j--;
}
[d[i], d[j]] = [d[j], d[i]];
let lo = i + 1, hi = d.length - 1;
while (lo < hi) {
[d[lo], d[hi]] = [d[hi], d[lo]];
lo++;
hi--;
}
const ans = Number(d.join(''));
return ans < 2 ** 31 ? ans : -1;
}