same idea as "next permutation." Start from back, find point where the previous digit is less than the current digit, look for the furthest right value that is greater than (which is also the smallest digit that is greater than) the previous digit, swap the two, then reverse the array from the current digit to the end.
def nextGreaterElement(self, n): if not n: return -1 s = str(n) arr = [c for c in s] i = len(arr)-1 while i > 0: prev = int(arr[i-1]) if int(arr[i]) > prev: j = i # looking for right position to swap while j < len(arr) and int(arr[j]) > prev: j += 1 arr[i-1], arr[j-1], j = arr[j-1], arr[i-1], len(arr)-1 # reverse array from pivot point til end while i < j: arr[i], arr[j] = arr[j], arr[i] i += 1; j -= 1 res = int(''.join(arr)) # check 32 bit constraint return -1 if res > 2147483647 else res i -= 1 return -1
Same idea, a little bit different implementation. Use sort for next permutation.
class Solution(object): def nextGreaterElement(self, n): """ :type n: int :rtype: int """ max_int = 2**31 - 1 s = str(n) for i in range(len(s) - 1, 0, -1): if s[i] > s[i - 1]: # possible swap for j in range(len(s) - 1, i - 1, -1): if s[j] > s[i-1]: break # s[j] as first one > s[i-1] new_s = s[:i-1] + s[j] + ''.join(sorted(s[i-1:j] + s[j+1:])) result = int(new_s) return result if result <= max_int else -1 return -1
@sylvanyang O(n2) and O(n) are the exact same thing, so it can't be one but not the other. Also, it's actually O(log2 n).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.