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