738. Monotone Increasing Digits

Version #1
The strategy is to scan from left most side to right most side
if chars[i] > chars[i + 1] -> we try to decrease the chars[i] by one
While we are walking backward, we keep checking that the digit that we have decreased before is valid or not
keep track of the last index that we decrease
Since the last index is the left most index and it has the biggest weight, we can set all digits on its right to be '9's

class Solution {
    public int monotoneIncreasingDigits(int N) {
char[] chars = String.valueOf(N).toCharArray();
int leftMost = -1;
for (int i = chars.length - 2; i >= 0; i--) {
if (chars[i] > chars[i + 1]) {
chars[i]--;
leftMost = i;
}
}
// all chars on the left side of leftMost index are valid
if (leftMost == -1) {
return N;
}
for (int i = leftMost + 1; i < chars.length; i++) {
chars[i] = '9';
}
return Integer.valueOf(new String(chars));
}
}