Welcome to Subscribe On Youtube

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

• Java
• C++
• Python
• Go

• 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);
      }
  };
  

• 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))
  
  

• 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
  }
  

All Problems

All Solutions