Math
Two Pointers
String
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
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 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 );
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 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 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 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
}
GitHub