刷刷刷 Day 37 | 738. 单调递增的数字

738. 单调递增的数字

LeetCode题目要求

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

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

示例

输入: n = 10
输出: 9

解题思路

以 98 为例，找到最大的比它小的递增数字是，89.
因为 9 > 8， 不是递增，那就得把 9 - 1 = 8 ，而 个人的 8 直接变成 9 ，那么能保证最大递增

上代码

class Solution {
    public int monotoneIncreasingDigits(int n) {
        
        String s = String.valueOf(n);
        char[] cs = s.toCharArray();

        // 需要补 9 的标记开始位置
        int start = s.length();

        // 从倒数第二个数开始
        for (int i = s.length() - 2; i >= 0; i--) {
            // 前面的比后面的大
            if (cs[i] > cs[i+1]) {
                cs[i]--;
                start = i+1;
            }
        }

        for (int i = start; i < s.length(); i++) {
            cs[i] = '9';
        }
        
        return Integer.parseInt(String.valueOf(cs));

    }
}

附：学习资料链接