738.Monotone Increasing Digits

1-

举个例子，比如33296这个数，先看6，因为9比6大，显然不符合Monotone定义，所以为了满足求得最大的num，6一定变成9，且9减1，所以这个数就变成了33289，同理此时2和3是不符合定义，于是又变成了32999，还是一样，最终就变成了29999。

再看一个例子：23296，根据上述的过程则变为22999。所以只要对其中的每一位减一，后续的几位都变成9，生成多个候选解，那么必然有一个解在其中。

http://blog.csdn.net/u014688145/article/details/78712104

从左到右找到相邻两个数字中digit[i] > digit[i+1]的索引i，对于i+1到digits.size()的数字全部置为9；

对于j在i到0之间依次找到digits[j] > digits[j + 1]，设置digits[j + 1] = 9;digits[j]--;其他情况直接跳出循环。

http://blog.csdn.net/u011809767/article/details/78749140

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] nums = String.valueOf(N).toCharArray();
        int n = nums.length;
        for(int i = n - 2; i >= 0; i--){
            //Find an invarient
            if(nums[i] > nums[i + 1]){
                nums[i] = (char) (nums[i] - 1);
                for(int j = i + 1; j < n; j++){
                    nums[j] = '9';
                }
            }
        }
        return Integer.valueOf(String.valueOf(nums));
    }
}