代码随想录——单调递增的数字（Leetcode738）

题目链接

贪心

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int flag = digits.length;
        
        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                flag = i;
                digits[i - 1]--;
            }
        }
        
        for (int i = flag; i < digits.length; i++) {
            digits[i] = '9';
        }
        
        return Integer.parseInt(new String(digits));
    }
}

本题使用暴力法会超时，贪心的思想为：
对给出的数字从后向前遍历，如果不符合单调递增则将不符合的位数字-1，之后的数字全部变为9