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.