单调递增的数字

题目

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

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

具体思路

• 将数字转换成字符串
• 字符串要从后往前遍历，因为从前向后遍历的结果不能保证在后面也成立
• 每遇到一个逆序，就把当前值的前一个减减，然后当前值置为要成为9的位置
• 因为每次遇到一个逆序，最新的会把旧的覆盖掉

具体代码

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        // 整体逻辑：如果乱序，当前i--,后一位及以后都置为9
        string s = to_string(n);
        int cur = s.size();
        for (int i = s.size() - 1; i >= 1; i--) {
            if (s[i] < s[i - 1]) {
                s[i - 1]--;
                cur = i;
            }
        }
        for (int i = cur; i < s.size(); i++) {
            s[i] = '9';
        }
        return stoi(s);
    }
};

class Solution {
    public int monotoneIncreasingDigits(int n) {
        String cur = Integer.toString(n);
        StringBuilder sb = new StringBuilder(cur);
        int flag = sb.length();
        for (int i = sb.length() - 1; i > 0; i--) {
            if (sb.charAt(i) < sb.charAt(i - 1)) {
                sb.setCharAt(i, '9');
                flag = i;
                sb.setCharAt(i - 1, (char) (sb.charAt(i - 1) - 1));
            }
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < sb.length(); i++) {
            if (i >= flag) {
                res.append('9');
            } else {
                res.append(sb.charAt(i));
            }
        }

        return Integer.parseInt(res.toString());
    }
}

// 1538 1238 1499 353 349 349 332 299 10 9

使用 StringBulider 来实现动态更改 String ，注意 String 类型是不可变的，所以一定要换成可变的 StringBuilder lai’sh