556. Next Greater Element III
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 <= 231 - 1
Rust Solution
struct Solution;
impl Solution {
fn next_greater_element(n: i32) -> i32 {
let mut s: Vec<char> = format!("{}", n).chars().collect();
let n = s.len();
let mut l = n;
for i in (0..n - 1).rev() {
if s[i] < s[i + 1] {
l = i;
break;
}
}
if l == n {
return -1;
}
let mut max = s[l + 1];
let mut r = l + 1;
for i in l + 2..n {
if s[i] > s[l] && s[i] < max {
max = s[i];
r = i;
}
}
s.swap(l, r);
s[l + 1..].sort_unstable();
s.iter().collect::<String>().parse::<i32>().unwrap_or(-1)
}
}
#[test]
fn test() {
let n = 12;
let res = 21;
assert_eq!(Solution::next_greater_element(n), res);
let n = 21;
let res = -1;
assert_eq!(Solution::next_greater_element(n), res);
let n = 1_999_999_999;
let res = -1;
assert_eq!(Solution::next_greater_element(n), res);
}
Having problems with this solution? Click here to submit an issue on github.