Description
Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such positive integer exists, return -1.
Note that the returned integer should fit in 32-bit integer, if there is a valid answer but it does not fit in 32-bit integer, return -1.
Example 1:
Input: n = 12
Output: 21
Example 2:
Input: n = 21
Output: -1
Constraints:
1 <= n <= 2^31 - 1
Solution
Solved after help…
Same as 31. 下一个排列
The next greater number should be: start from the rightmost, and until we find a digit that is smaller than at least one of the digits we have visited, we should swap the digit with the minimum but larger digit of all the digits we have visited. Then sort all the digits at the right. Then we would get our answer.
Time complexity: o ( n log n ) o(n\log n) o(nlogn)
Space complexity: o ( n ) o(n) o(n)
Code
class Solution:def nextGreaterElement(self, n: int) -> int:num_list = []while n > 0:num_list.append(n % 10)n //= 10stack = []for i in range(len(num_list)):if not stack or num_list[stack[-1]] <= num_list[i]:stack.append(i)else:swap_index = stack[-1]# swap current number with previous minimum larger onewhile stack and num_list[stack[-1]] > num_list[i]:swap_index = stack.pop()num_list[i], num_list[swap_index] = num_list[swap_index], num_list[i]num_list[:i] = sorted(num_list[:i], reverse=True)i = len(num_list) + 1breakif i == len(num_list) + 1:res = eval(''.join(map(str, num_list[::-1])))if res > 2 ** 31 - 1:res = -1else:res = -1return res
