难度: Medium
给你一个正整数 n ，请你找出符合条件的最小整数，其由重新排列 n 中存在的每位数字组成，并且其值大于 n 。如果不存在这样的正整数，则返回 -1 。
注意 ，返回的整数应当是一个 32 位整数 ，如果存在满足题意的答案，但不是 32 位整数 ，同样返回 -1 。
示例 1：
输入：n = 12 输出：21
示例 2：
输入：n = 21 输出：-1
提示：
1 <= n <= 231 - 1
Submission
运行时间: 19 ms
内存: 16.1 MB
class Solution:
def nextGreaterElement(self, n: int) -> int:
digits = []
while n > 0:
digits.insert(0, n%10)
n //= 10
size, idx = len(digits), -1
for i in range(size-2, -1, -1):
if digits[i] < digits[i+1]:
idx = i
break
if idx < 0:
return -1
for i in range(size-1, idx, -1):
if digits[i] > digits[idx]:
digits[idx], digits[i] = digits[i], digits[idx]
digits = digits[0:idx+1] + digits[-1:idx:-1]
break
ans, limit = 0, pow(2, 31) - 1
for d in digits:
if ans > (limit - d) / 10:
return -1
ans = ans * 10 + d
return ans
Explain
该题解的思路是：首先将整数 n 的每一位数字存入数组 digits 中。然后从数组末尾开始向前遍历，找到第一个满足 digits[i] < digits[i+1] 的位置 idx。如果找不到这样的位置，说明整数 n 已经是最大的排列，直接返回 -1。否则，再从数组末尾开始向前遍历，找到第一个满足 digits[i] > digits[idx] 的位置 i，交换 digits[idx] 和 digits[i]，然后将 digits[idx+1:] 部分翻转。最后，将数组 digits 转换成整数 ans，并检查是否超出了 32 位整数的范围。如果超出范围，返回 -1，否则返回 ans。
时间复杂度: O(log n)
空间复杂度: O(log n)
class Solution:
def nextGreaterElement(self, n: int) -> int:
# 将整数 n 的每一位数字存入数组 digits 中
digits = []
while n > 0:
digits.insert(0, n%10)
n //= 10
size, idx = len(digits), -1
# 从数组末尾开始向前遍历，找到第一个满足 digits[i] < digits[i+1] 的位置 idx
for i in range(size-2, -1, -1):
if digits[i] < digits[i+1]:
idx = i
break
# 如果找不到这样的位置，说明整数 n 已经是最大的排列，直接返回 -1
if idx < 0:
return -1
# 从数组末尾开始向前遍历，找到第一个满足 digits[i] > digits[idx] 的位置 i
for i in range(size-1, idx, -1):
if digits[i] > digits[idx]:
# 交换 digits[idx] 和 digits[i]
digits[idx], digits[i] = digits[i], digits[idx]
# 将 digits[idx+1:] 部分翻转
digits = digits[0:idx+1] + digits[-1:idx:-1]
break
ans, limit = 0, pow(2, 31) - 1
# 将数组 digits 转换成整数 ans，并检查是否超出了 32 位整数的范围
for d in digits:
if ans > (limit - d) / 10:
return -1
ans = ans * 10 + d
return ans
Explore
选择寻找第一个 digits[i] < digits[i+1] 的位置作为交换起点是为了找到当前数值从后向前的第一个递减的位置，这标志着可以通过交换产生一个更大的数值。这个点是从右向左第一个可以增加的'拐点'，通过在这个点进行操作，我们可以保证在这个点之后的数值是递减的，从而找到一个稍大的元素进行交换，以获得下一个更大的排列。
执行交换后，digits[idx+1:] 部分还是保持之前的递减顺序。为了获得最小的下一个更大的数，需要将这部分翻转变为递增顺序。这样，整体数值才是仅次于原数的最小数，即下一个更大的元素。翻转确保了在保持前半部分尽可能小的同时，后半部分是最小的可能排列。
数组的翻转可以通过多种方式实现，如使用双指针法从两端开始交换元素直到中间，或使用现成的库函数。不同的实现方式在效率上可能有细微差别，但对于解题来说，最终效果相同，即获得递增的子数组。主要的区别在于代码的简洁性和执行的效率。
为了确保不超出 32 位整数的范围，代码中实现了对结果的每一步乘法和加法前进行范围检查。具体地，通过判断 ans 是否大于 (limit - d) / 10 来预判加上新的数字后是否会超过 32 位整数的上限。这种方法是通过数学推导保证在执行乘法和加法之前，结果不会溢出。