Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/738.html

738. Monotone Increasing Digits

Level

Medium

Description

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].

Solution

Compare each pair of adjacent digits of N from right to left. If the left digit is greater than the right digit, decrease the left digit by 1 so that the left digit has the greatest possible value to have a number with monotone increasing digits at the current time. After the most significant digit that needs to decrease is determined, decrease the most significant digit by 1, and set all the lower digits to 9.

• Java
• C++
• Python

• class Solution {
      public int monotoneIncreasingDigits(int N) {
          char[] numArray = String.valueOf(N).toCharArray();
          int firstIndex = -1;
          int length = numArray.length;
          for (int i = length - 1; i > 0; i--) {
              if (numArray[i] < numArray[i - 1]) {
                  firstIndex = i - 1;
                  numArray[i - 1]--;
              }
          }
          if (firstIndex < 0)
              return N;
          else {
              for (int i = firstIndex + 1; i < length; i++)
                  numArray[i] = '9';
          }
          String numStr = new String(numArray);
          return Integer.parseInt(numStr);
      }
  }
  

• // OJ: https://leetcode.com/problems/monotone-increasing-digits/
  // Time: O(log_10^N)
  // Space: O(log_10^N)
  class Solution {
  public:
      int monotoneIncreasingDigits(int n) {
          vector<int> v;
          while (n) {
              v.push_back(n % 10);
              n /= 10;
          }
          int i = v.size() - 2, ans = 0;
          for (; i >= 0 && v[i] >= v[i + 1]; --i);
          if (i >= 0) {
              while (i + 2 < v.size() && v[i + 1] == v[i + 2]) ++i;
              v[i + 1]--;
              while (i >= 0) v[i--] = 9;
          }
          while (v.size()) {
              ans = ans * 10 + v.back();
              v.pop_back();
          }
          return ans; 
      }
  };
  

• 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:
      def monotoneIncreasingDigits(self, N):
          """
          :type N: int
          :rtype: int
          """
          if N < 10: return N
          num = [int(n) for n in str(N)[::-1]]
          n = len(num)
          ind = -1
          for i in range(1, n):
              if num[i] > num[i - 1] or (ind != -1 and num[i] == num[ind]):
                  ind = i
          if ind == -1:
              return N
          res = '9' * ind + str(num[ind] - 1) + "".join(map(str, num[ind + 1:]))
          return int(res[::-1])
  

All Problems

All Solutions