Problem
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 <= 10^9
Solution (Java)
class Solution {
public int monotoneIncreasingDigits(int n) {
for (int i = 10; n / i > 0; i *= 10) {
int digit = (n / i) % 10;
int endnum = n % i;
int firstendnum = endnum * 10 / i;
if (digit > firstendnum) {
n -= endnum + 1;
}
}
return n;
}
}
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).