贪心

class Solution {
    public int monotoneIncreasingDigits(int n) {

        /**
         * 将数字拆分为字符数组
         * start为第一个需要变为9的位置，后面的位置全部要变为9
         */
        char[] chars = String.valueOf(n).toCharArray();
        int start = chars.length;

        /**
         * 从后往前遍历
         * 如果当前位置小于前一个位置，说明从当前位置开始以后的所有位置都要变成9
         * 但是不能在循环中直接赋值9，因为可能这段区间内有递增序列，这样就不会被赋值
         * 所以需要记录最远的开始变为9的索引，最后一次性赋值9
         */
        for (int i = chars.length - 1; i > 0; i--) {

            if (chars[i - 1] > chars[i]){

                chars[i - 1]--;
                start = i;
            }
        }

        for (int i = start; i < chars.length; i++) {
            chars[i] = '9';
        }

        return Integer.parseInt(new String(chars));
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(n)
 */

https://leetcode-cn.com/problems/monotone-increasing-digits/