Concretely, if all the bits are in decreasing order, for example, 4321, then there would be no next greater element. If we have a number like 12431, then we need to exchange 3 with 2, 13421. Now 3 is definitely at its rightful position. We only need to see what is the smallest number formed by 4, 2, 1, which is 124.
Program above idea: suppose our number in its string format is
ns is the highest bit. We scan from the lowest bit until we encounter the bit i where
ns[i] < ns[i+1], then we exchange
j is the lowest bit that satisfies
ns[i] < ns[j]. After this, we can be sure that bit
i is right, then we need to sort
class Solution(object): def nextGreaterElement(self, n): """ :type n: int :rtype: int """ ns = [s for s in str(n)] for i in range(len(ns)-2, -1, -1): if ns[i] < ns[i+1]: j = len(ns) - 1 while ns[j] <= ns[i]: # need to find ns[i] < ns[j] where j is the lowest possible bit j -= 1 ns[i], ns[j] = ns[j], ns[i] ns[i+1:] = sorted(ns[i+1: ]) return int(''.join(ns)) if int(''.join(ns)) < 2**31 - 1 else -1 return -1