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:
class Solution {
/*
The result should be:
preceding monotone increasing digits (ending digit should decrease by 1)
followed by
all remaining digits set to '9'
.
e.g. N = 12321, the result is 12299.
monotoneIncreasingEnd is finalized as : 2
current arrN : 12211
arrN is finalized as : 12299
*/
public int monotoneIncreasingDigits(int N) {
char[] str = Integer.toString(N).toCharArray();
int len = str.length;
int monoIncreaseEnd = len;
for (int i = len - 1; i > 0; i --) {
if (str[i - 1] > str[i]) {
monoIncreaseEnd = i;
str[i - 1] --;
}
}
for (int i = monoIncreaseEnd; i < len; i ++) {
str[i] = '9';
}
return Integer.parseInt(new String(str));
}
}