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.