Monotone increasing digits

Math Greedy

49.4% acceptance

Feb 21, 2026

1405

115

An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y. Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

/*
 * An integer has monotone increasing digits if and only if each pair of adjacent digits x and y satisfy x <= y.
 * Given an integer n, return the largest number that is less than or equal to n with monotone increasing digits.
 * Example 1:
 * Input: n = 10
 * Output: 9
 * Example 2:
 * Input: n = 1234
 * Output: 1234
 * Example 3:
 * Input: n = 332
 * Output: 299
 * Constraints:
 * 0 <= n <= 109
 */
impl Solution {
  pub fn monotone_increasing_digits(n: i32) -> i32 {
    let mut digits: Vec<u8> = n.to_string().bytes().collect();
    let len = digits.len();
    let mut mark = len; // position from which we fill 9s
    let mut i = len - 1;
    while i > 0 {
      if digits[i] < digits[i-1] {
        digits[i-1] -= 1;
        mark = i;
      }
      i -= 1;
    }
    for j in mark..len {
      digits[j] = b'9';
    }
    std::str::from_utf8(&digits).unwrap().parse().unwrap()
  }
}