单调递增的数字

给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/monotone-increasing-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心算法

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] num = Integer.toString(N).toCharArray();
        for (int i = 0; i + 1 < num.length; i++) {
            if (num[i] > num[i + 1]) {//如果前一位大于后一位
                num[i]--;//前一位减一
                for (int j = i; j - 1 >= 0; j--) {//去查看当前位之前的元素是不是小于当前的位，如果不满足，要修改更靠前的位
                    if (num[j - 1] > num[j]) {
                        num[j - 1]--;
                        num[j] = '9';
                    }else {
                        break;
                    }
                }
                for (int j = i + 1; j < num.length; j++) {//i后面的所有元素都要变成9
                    num[j] = '9';
                }
                break;
            }
        }

        String s = String.valueOf(num);
        return Integer.valueOf(s);
    }
}

贪心算法

class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] strN = Integer.toString(N).toCharArray();
        int i = 1;
        while (i < strN.length && strN[i - 1] <= strN[i]) {//先跳到第一个前一位大于后一位的位置
            i += 1;
        }
        if (i < strN.length) {
            while (i > 0 && strN[i - 1] > strN[i]) {//在这一位向前检查修改后的数字是否小于更前一位的数字，如果小于继续向前
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length; ++i) {//对这一位往后的元素都变成最大数字9
                strN[i] = '9';
            }
        }
        return Integer.parseInt(new String(strN));
    }
}

参考文献

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/monotone-increasing-digits/solution/dan-diao-di-zeng-de-shu-zi-by-leetcode-s-5908/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

赏

谢谢你请我吃糖果

微信