单调递增的数字 图解题解

这道题到底在问什么

n

332

输出

299

为什么

332 不递增(3>2);299 是 ≤332 里最大的递增数

最优解：一步一步想明白

1. 3n 可能很大(到 10 位数),一个个往下试要试几亿次,必然超时。得找规律。
2. 4把「左位减 1、右边全填 9」记牢。减 1 是为了变小到 ≤n,填 9 是为了在变小的前提下尽量大。下面一帧帧演给你看。
3. 5把数字按位排开把 332 拆成三位数字 [3, 3, 2] 排成一排,下标 0、1、2。我们要从最右边的相邻对开始,一对对往左查「有没有下坡」。
4. 6比较 s[1]=3 与 s[2]=2指针落在最右位 下标 2,看它和左边邻居 下标 1 这一对。问:左边 3 是不是大于右边 2?
5. 7左位 s[1] 减 1,记 mark=23 > 2,是下坡!按规律:左边这位 3 减 1 变成 2(数字真的变了),并记下 mark=2——意思是「从下标 2 开始往后都要填 9」。
6. 8比较 s[0]=3 与 s[1]=2指针往左挪到 下标 1,看它和更左的 下标 0 这一对。注意此刻 s[1] 已经是刚减过的 2。再问:3 > 2 吗?
7. 9左位 s[0] 减 1,mark 更新为 1又是下坡!s[0] 由 3 减为 2,mark 更新成 1(因为减 1 发生在更左边,填 9 的起点也要跟着左移)。数字现在是 [2, 2, 2]。
8. 10没有更左的邻居指针到了最左位,再没有「左边邻居」可比,比较阶段结束。现在数字是 [2, 2, 2],记着的 mark = 1。下一步:从 mark 开始填 9。
9. 11从 mark=1 起填 9进入填 9 阶段:从 mark=1 这位开始,下标 1 改成 9。为什么填 9?因为前面减了 1 已经保证比 n 小,后面就该尽量大,9 最大。
10. 12继续填到末尾再把 下标 2 也改成 9。填到末尾,数字变成 [2, 9, 9],也就是 299——正是答案!
11. 13完成检验:2 ≤ 9 ≤ 9 确实单调递增,且不超过 332。一次从右往左的扫描就拿到了答案 299。
12. 14本来就递增换个数 1234 看看「本来就递增」会怎样。同样从最右一对开始往左查下坡。
13. 15下标 2 与 3最右一对 3 和 4:3 < 4,不是下坡,什么都不改,指针往左挪。
14. 16下标 1 与 2再往左一对 2 和 3:还是 2 < 3,不是下坡,继续左移。
15. 17下标 0 与 1最左一对 1 和 2:依旧 1 < 2。全程没找到下坡,mark 始终为「无」。
16. 18本来递增,原样返回既然没下坡,就不减也不填,1234 本身已经单调递增,直接返回 1234。
17. 19会出现前导 0看一个易错例 10:最右一对 1 和 0,1 > 0 是下坡。左位要减 1。
18. 20s[0]→0, s[1]→9s[0] 减成 0,mark=1 让 s[1] 填 9,字符串变成 "09"。注意最高位成了 前导 0!
19. 21转回整数,前导 0 自然消失把 "09" 转回整数,前导 0 自动消失(下标 0 那位被丢弃,变灰),得到 9。所以代码最后用「转整数」一步天然处理了前导 0,不用特判。
20. 22先无下坡,后出下坡再看 100。最右一对是 0 和 0,相等不算下坡(要求是「左 > 右」),不改,指针左移。
21. 231 > 0 是下坡往左一对 1 和 0:1 > 0 是下坡!左位要减 1,并记 mark。
22. 24s[0]→0,mark=1s[0] 由 1 减成 0,记下 mark=1。数字暂时是 [0, 0, 0]。
23. 25下标 1、2 → 9从 mark=1 起把下标 1、2 都填 9,得到 "099",转整数去掉前导 0 → 99。
24. 26如果从左往右,改了前面的位,后面已经检查过的就可能又被破坏、来不及补救。从右往左保证每次改动只影响「更左、还没查的」位,一遍扫描就够。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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 自然消失

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);
    }
};

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));
    }
}

复杂度

面试官可能追问