单调递增的数字 图解题解

求 ≤n 的最大数，还要各位从左到右不下降

给一个整数 n，要返回不超过 n、且各位数字单调递增的最大整数——单调递增就是从左到右每一位都不大于右边那位，像 1234、1359 都算。题面给 n=332，答案是 299：332 自己中间的 3 比右边的 2 大、不满足，而 299 是 ≤332 的递增数里最大的一个。

从 n 往下一个个试，为什么会超时

n 能到 10 位数，要是从 n 开始一个一个往下减、每个都拆开检查是不是递增，最坏得试上亿次才碰到答案，交上去必然超时。所以不能挨个验，得看出数字本身的规律，一遍扫描就定位到答案。

出现下降，该把哪位动手、动成什么样

盯住相邻两位：只要左边一位比右边大，这个数在这里就下降了，必须改。改法是把左边那位减 1，减 1 是为了把整个数压到 ≤n；可光减 1 会让它变得没必要地小，所以从被减的这位往后，全部填成 9——在已经比 n 小的前提下，每位取到最大的 9，整个数才尽量大。这种见下降就把左位借走 1、其后全填 9 顶到最大的改法，就是贪心：每一处改动都在当前局面下把数做到能做的最大。

为什么这一遍必须从右往左扫

把 n 拆成一排数字，从最右边相邻的一对开始、向左逐对检查：遇到左位＞右位就把左位减 1、并记下这个位置 mark（表示从这位起后面都要填 9）。为什么方向不能反？因为减 1 只会在更左边引出新的下降：332 把中间的 3 减成 2 后，最左的 3 又比它大了。从右往左走，新冒出来的下降都落在还没检查的左侧，会被接着处理；要是从左往右，改了前面、后面已检查过的又被破坏，来不及补救。扫完再从 mark 一路填 9 到末尾。

332 是怎么一步步变成 299 的

拆成 [3, 3, 2]，下标 0、1、2，mark 先记成 3（3 已越过最后一位、代表眼下没有要填 9 的位置）。从右往左：先看下标 1 和 2，3＞2 是下降，把下标 1 的 3 减成 2、mark=2。再往左看下标 0 和 1，此时下标 1 已是 2，3＞2 还是下降，下标 0 的 3 减成 2、mark=1。到最左没有邻居了，扫描停，数字成了 [2, 2, 2]、mark=1。接着从 mark=1 起填 9：下标 1、下标 2 都改成 9，得到 [2, 9, 9]，转成整数就是 299。

这题最常见的三种写错

方向反了最隐蔽：从左往右扫，减 1 引出的连锁下降会被漏掉，332 就算不出 299，只能从右往左。填 9 也别抠着减 1 那一位的右边只补一格，减 1 发生在最左时，它右边每一位都得填成 9，整个数才最大，所以要从 mark 铺到末尾。还有 n=10 这种，中途会得到「09」，别慌着特判，最后统一转成整数，前导 0 自然消失、结果就是 9。复杂度上只扫数字的位数、最多十来位，时间 O(len)；把数字拆成字符存下来占 O(len) 空间。

Python

class Solution:
    def monotoneIncreasingDigits(self, n):
        s = list(str(n))            # 拆成各位数字字符
        mark = len(s)               # 从这一位起填 9, 初始无
        for i in range(len(s) - 1, 0, -1):   # 从右往左
            if s[i - 1] > s[i]:     # 发现下坡
                s[i - 1] = str(int(s[i - 1]) - 1)  # 左位减 1
                mark = i            # 记下填 9 起点
        for i in range(mark, len(s)):  # 从 mark 起全填 9
            s[i] = '9'
        return int(''.join(s))      # 转整数, 前导 0 自然消失

C++

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string s = to_string(n);
        int mark = s.size();           // 从此位起填 9
        for (int i = s.size() - 1; i > 0; i--) {  // 从右往左
            if (s[i - 1] > s[i]) {     // 下坡
                s[i - 1]--;            // 左位减 1
                mark = i;
            }
        }
        for (int i = mark; i < (int)s.size(); i++) s[i] = '9';
        return stoi(s);
    }
};

Java

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] s = String.valueOf(n).toCharArray();
        int mark = s.length;               // 从此位起填 9
        for (int i = s.length - 1; i > 0; i--) {   // 从右往左
            if (s[i - 1] > s[i]) {         // 下坡
                s[i - 1]--;                // 左位减 1
                mark = i;
            }
        }
        for (int i = mark; i < s.length; i++) s[i] = '9';
        return Integer.parseInt(new String(s));
    }
}