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:
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def nextGreaterElement(self, n: int) -> int:
cs = list(str(n))
n = len(cs)
i, j = n - 2, n - 1
while i >= 0 and cs[i] >= cs[i + 1]:
i -= 1
if i < 0:
return -1
while cs[i] >= cs[j]:
j -= 1
cs[i], cs[j] = cs[j], cs[i]
cs[i + 1 :] = cs[i + 1 :][::-1]
ans = int(''.join(cs))
return -1 if ans > 2**31 - 1 else ans(code-box)
class Solution {
public int nextGreaterElement(int n) {
char[] cs = String.valueOf(n).toCharArray();
n = cs.length;
int i = n - 2, j = n - 1;
for (; i >= 0 && cs[i] >= cs[i + 1]; --i)
;
if (i < 0) {
return -1;
}
for (; cs[i] >= cs[j]; --j)
;
swap(cs, i, j);
reverse(cs, i + 1, n - 1);
long ans = Long.parseLong(String.valueOf(cs));
return ans > Integer.MAX_VALUE ? -1 : (int) ans;
}
private void swap(char[] cs, int i, int j) {
char t = cs[i];
cs[i] = cs[j];
cs[j] = t;
}
private void reverse(char[] cs, int i, int j) {
for (; i < j; ++i, --j) {
swap(cs, i, j);
}
}
}(code-box)
class Solution {
public:
int nextGreaterElement(int n) {
string s = to_string(n);
n = s.size();
int i = n - 2, j = n - 1;
for (; i >= 0 && s[i] >= s[i + 1]; --i)
;
if (i < 0) return -1;
for (; s[i] >= s[j]; --j)
;
swap(s[i], s[j]);
reverse(s.begin() + i + 1, s.end());
long ans = stol(s);
return ans > INT_MAX ? -1 : ans;
}
};(code-box)
func nextGreaterElement(n int) int {
s := []byte(strconv.Itoa(n))
n = len(s)
i, j := n-2, n-1
for ; i >= 0 && s[i] >= s[i+1]; i-- {
}
if i < 0 {
return -1
}
for ; j >= 0 && s[i] >= s[j]; j-- {
}
s[i], s[j] = s[j], s[i]
for i, j = i+1, n-1; i < j; i, j = i+1, j-1 {
s[i], s[j] = s[j], s[i]
}
ans, _ := strconv.Atoi(string(s))
if ans > math.MaxInt32 {
return -1
}
return ans
}(code-box)
