代码随想录——单调递增的数字(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

上一篇:Adversarial Reweighting for Partial Domain Adaptation(论文阅读)


下一篇:ROS melodic版本卸载---Ubuntu18.04