Question

738. Monotone Increasing Digits

中文文档

Description

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

Solutions

Solution 1

class Solution:
  def monotoneIncreasingDigits(self, n: int) -> int:
    s = list(str(n))
    i = 1
    while i < len(s) and s[i - 1] <= s[i]:
      i += 1
    if i < len(s):
      while i and s[i - 1] > s[i]:
        s[i - 1] = str(int(s[i - 1]) - 1)
        i -= 1
      i += 1
      while i < len(s):
        s[i] = '9'
        i += 1
    return int(''.join(s))

class Solution {
  public int monotoneIncreasingDigits(int n) {
    char[] s = String.valueOf(n).toCharArray();
    int i = 1;
    for (; i < s.length && s[i - 1] <= s[i]; ++i)
      ;
    if (i < s.length) {
      for (; i > 0 && s[i - 1] > s[i]; --i) {
        --s[i - 1];
      }
      ++i;
      for (; i < s.length; ++i) {
        s[i] = '9';
      }
    }
    return Integer.parseInt(String.valueOf(s));
  }
}

class Solution {
public:
  int monotoneIncreasingDigits(int n) {
    string s = to_string(n);
    int i = 1;
    for (; i < s.size() && s[i - 1] <= s[i]; ++i)
      ;
    if (i < s.size()) {
      for (; i > 0 && s[i - 1] > s[i]; --i) {
        --s[i - 1];
      }
      ++i;
      for (; i < s.size(); ++i) {
        s[i] = '9';
      }
    }
    return stoi(s);
  }
};

func monotoneIncreasingDigits(n int) int {
  s := []byte(strconv.Itoa(n))
  i := 1
  for ; i < len(s) && s[i-1] <= s[i]; i++ {
  }
  if i < len(s) {
    for ; i > 0 && s[i-1] > s[i]; i-- {
      s[i-1]--
    }
    i++
    for ; i < len(s); i++ {
      s[i] = '9'
    }
  }
  ans, _ := strconv.Atoi(string(s))
  return ans
}