738. Monotone Increasing Digits

Given a non-negative integer N, find the largest number that is less than or equal to N with monotone increasing digits.

(Recall that an integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.)

Example 1:

Input: N = 10
Output: 9

Example 2:

Input: N = 1234
Output: 1234

Example 3:

Input: N = 332
Output: 299

Note: N is an integer in the range [0, 10^9].

Rust Solution

struct Solution;

impl Solution {
    fn monotone_increasing_digits(n: i32) -> i32 {
        let mut s: Vec<char> = n.to_string().chars().collect();
        let n = s.len();
        let mut i = 1;
        while i < n && s[i] >= s[i - 1] {
            i += 1;
        }
        while i > 0 && i < n && s[i - 1] > s[i] {
            s[i - 1] = (s[i - 1] as u8 - 1) as char;
            i -= 1;
        }
        while i + 1 < n {
            s[i + 1] = '9';
            i += 1;
        }
        s.into_iter().collect::<String>().parse::<i32>().unwrap()
    }
}

#[test]
fn test() {
    let n = 10;
    let res = 9;
    assert_eq!(Solution::monotone_increasing_digits(n), res);
    let n = 1234;
    let res = 1234;
    assert_eq!(Solution::monotone_increasing_digits(n), res);
    let n = 332;
    let res = 299;
    assert_eq!(Solution::monotone_increasing_digits(n), res);
}

Having problems with this solution? Click here to submit an issue on github.