738. 单调递增的数字

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

给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

• 0 <= n <= 10^9

贪心

从右向左在 n 中找到第一个破坏单调递增性质的位置，然后将该位置及之后的所有数字都变为 9，之前的数字递减 1。最后将处理后的数组重新拼接成一个整数并返回。 举例332，从右往左，首先是2，再3，2比3小，不符合递增，所以将前一个数减1，也就是3-1变2，2的位置变9，此时变成329，再继续检查， 3,2，又不符合了，所以3-1变2,2变9，最后结果就是299

class Solution {
    public int monotoneIncreasingDigits(int N) {
        // 将整数 N 转换为字符串，再转换为字符数组
        char[] arr = Integer.toString(N).toCharArray();

        int len = arr.length;
        int marker = len; // 用于标记需要改为 '9' 的开始位置

        // 倒序遍历字符数组
        for (int i = len - 1; i > 0; i--) {
            if (arr[i] < arr[i - 1]) {
                // 如果发现当前数字小于前一个数字
                // 将前一个数字减 1，只需减一即可，例如342，4只需减到3，不需要减到2，因为2要变成9。
                // 注意下次判断的是减完后的arr[i-1]。逐步调整。磨光法。
                arr[i - 1]--;
                // 标记需要改为 '9' 的开始位置
                marker = i;
            }
        }

        // 将从 marker 开始的所有数字改为 '9'，注意是从marker开始而不是marker+1开始
        for (int i = marker; i < len; i++) {
            arr[i] = '9';
        }

        // 将字符数组转换回整数并返回
        return Integer.parseInt(new String(arr));
    }
}

• 时间复杂度： $O(\log n)$ ，其中 $O(\log n)$ 表示数字 $n$ 的位数。我们遍历 $O(\log n)$ 的时间即能构造出满足条件的数字。
• 空间复杂度： $O(\log n)$ 。我们需要 $O(\log n)$ 的空间存放数字 $n$ 每一位的数字大小。