文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Next Greater Element III
2. Solution
解析：Version 1，先将数字n变为字符数组，要找最小的大于n的数，则应该从右往左开始，依次寻找第i位字符右边的大于当前字符的最小数字，然后互换二者位置，由于新数字的第i位字符大于n中的第i位字符，因此新数字i位之后的字符应该从小到大排列，这样可以保证新数字是最小的大于n的数字。当每一个字符都大于其右边的字符时，则找不到大于n的数字，返回-1。如果新数字大于2^31-1，也应该返回-1。Version 2，先找可以跟右边数字互换的字符digits[i]，即右边存在大于它的字符。连续比较两个相邻字符，保证了digits[i]右边的字符从大到小的关系。找到之后，再从右边寻找大于digits[i]的最小字符digits[j]，由于右边字符从大到小的关系，因此只要字符digits[j]大于digits[i]，digits[j]就是大于digits[i]的最小字符。
- Version 1
class Solution:
def nextGreaterElement(self, n: int) -> int:
digits = list(str(n))
for i in range(len(digits) - 1, -1, -1):
index = i
for j in range(i+1, len(digits)):
if digits[i] < digits[j] and (index == i or digits[j] < digits[index]):
index = j
if index != i:
break
digits[i], digits[index] = digits[index], digits[i]
result = int(''.join(digits[:i+1] + sorted(digits[i+1:])))
if index == 0 or result > 2147483647:
return -1
return result
- Version 2
class Solution:
def nextGreaterElement(self, n: int) -> int:
digits = list(str(n))
i = len(digits) - 2
while i > -1 and digits[i] >= digits[i+1]:
i -= 1
if i == -1:
return -1
j = i + 1
while j < len(digits) and digits[j] > digits[i]:
j += 1
j -= 1
digits[i], digits[j] = digits[j], digits[i]
result = int(''.join(digits[:i+1] + sorted(digits[i+1:])))
result = -1 if result > 2147483647 else result
return result
