LeetCode 738. 单调递增的数字

2025-10-21 HGNULB 约 8 分钟

文章信息 7 个分类 2 个标签

分类

题目描述

✅ 738. 单调递增的数字

题意分析

给一个非负整数 n，要在所有不超过 n 的非负整数里，挑出十进制各位「从左到右不下降」的最大的那个。

首先要读准「单调递增」在本题里的含义。题面说的是任意相邻两位满足 $x \le y$，也就是允许相等，299 和 1111 都算合法。理解成严格递增会把绝大多数答案排除掉。

约束信号有两处。第一，n 的上界是 $10^9$，位数最多 10 位，所以按位处理的开销可以忽略，反而是「从 n 往下逐个试」这种做法有超时风险。第二，答案必须不超过 n，这是一个上界约束，意味着我们只能在 n 的基础上「往小调」，不能凭空构造。

边界上要留心：n 本身已经合法（如 1234，直接返回原值）、n 是一位数（永远合法）、修正后出现前导零（如 n = 10 得到 09，要还原成 9）、以及一次减一会引发左侧连锁下降的情形（如 n = 332）。

解法：从右向左修正

核心思路

最暴力的做法是从 n 开始往下逐个检查每个数是否满足单调不降，第一个满足的就是答案。这看上去在很多用例上跑得挺快，但用例 n = 111111110 的答案是 99999999，中间要跳过一千一百多万个数，直接超时。

瓶颈在于逐个试探完全没有利用「哪一位坏了」这个信息。观察答案的结构：设 n 从左数第一个「比右邻大」的位置在下标 i - 1（即 $digits[i-1] > digits[i]$），那么答案在下标 i - 1 之前必须与 n 完全相同或者更小。如果保持前缀不变，第 i - 1 位就卡死了，后面无论怎么填都无法既不下降又不超过 n；所以只能把第 i - 1 位减一，一旦这一位严格小于 n 的对应位，后面的位就彻底摆脱了上界约束，可以自由地取最大值 9。

于是修正的动作固定为两步：某一位减一，它右边全部填 9。麻烦在于减一之后可能制造出新的下降。比如 332 在下标 1 处减一变成 322，此时下标 0 的 3 又大于下标 1 的 2 了。

解决办法是从右向左扫描。每次只看相邻的一对，发现 $digits[i-1] > digits[i]$ 就把 digits[i - 1] 减一并把填 9 的起点 mark 更新为 i；因为扫描方向是从右往左，下一轮马上会检查 digits[i - 2] 和刚刚被减小的 digits[i - 1]，连锁下降会被自然地一路传播到最左边。而 mark 每次都被覆盖成更小的下标，最终停在最左边那次修正的位置上，正好是需要填 9 的最长后缀起点。

显式的不变量是：从右往左扫到位置 i 时，下标 i 到末尾这一段已经不存在任何下降对（更准确地说，这一段最终会被全部填成 9，而 mark 记录了这个后缀的起点）。扫描结束后把 [mark, end) 全部置为 9，前缀部分则天然满足不下降。

解题步骤

把 n 转成十进制字符数组。按位操作比反复做除法取模更直观，也方便原地修改。

令 mark = digits.length，表示「暂时没有任何一位需要填 9」。初值必须是数组长度而不是 0，否则在 n 本身就合法时会把整个数字填成全 9。

从 i = digits.length - 1 向左遍历到 i = 1，每轮比较 digits[i - 1] 和 digits[i]。下界取 1 是因为要访问 i - 1，取 0 会读到负下标。

若 digits[i - 1] > digits[i]，把 digits[i - 1] 减一，并令 mark = i。减的是左边那位而不是右边那位：只有让高位变小，才能既保证结果小于 n，又让低位获得填 9 的自由。

这里不需要判断「减完之后是不是又坏了」，因为下一轮循环就是拿 digits[i - 2] 和减完的 digits[i - 1] 比较，连锁会自动被捕获。

扫描结束后，把下标 mark 到末尾的所有位全部改成 9。起点是 mark 本身而不是 mark + 1：mark 位上的原值属于「已经失去上界约束」的部分，填 9 只会更大更优。

把字符数组转回整数返回。转整数这一步顺带解决了前导零："09" 会被解析成 9。

以 n = 332 走一遍：字符数组是 ['3', '3', '2']，mark = 3。

i = 2：比较 digits[1] = '3' 和 digits[2] = '2'，3 > 2 成立，把 digits[1] 减成 '2'，mark 更新为 2。数组变成 ['3', '2', '2']。

i = 1：比较 digits[0] = '3' 和刚刚被改过的 digits[1] = '2'，3 > 2 成立，把 digits[0] 减成 '2'，mark 更新为 1。数组变成 ['2', '2', '2']。这一步正是连锁修正被从右向左的扫描顺序自动接住的地方。

循环结束，从下标 1 开始填 9：digits[1] 和 digits[2] 都变成 '9'，数组是 ['2', '9', '9']，转回整数得 299。检验一下：299 <= 332，且 2 <= 9 <= 9 满足不下降，正确。

再看前导零的用例 n = 10：数组是 ['1', '0']，mark = 2。i = 1 时 1 > 0 成立，digits[0] 减成 '0'，mark = 1。填 9 后数组是 ['0', '9']，字符串 "09" 解析成整数正是 9。

再看无需修改的用例 n = 1234：i = 3、2、1 三轮比较分别是 3 > 4、2 > 3、1 > 2，全部不成立，mark 始终是 4。填 9 的循环从下标 4 起，一次都不执行，返回 1234。

代码实现

class Solution {
    public int monotoneIncreasingDigits(int n) {
        char[] digits = String.valueOf(n).toCharArray();
        int mark = digits.length;
        for (int i = digits.length - 1; i > 0; i--) {
            if (digits[i - 1] > digits[i]) {
                digits[i - 1]--;
                mark = i;
            }
        }
        for (int i = mark; i < digits.length; i++) {
            digits[i] = '9';
        }
        return Integer.parseInt(new String(digits));
    }
}

func monotoneIncreasingDigits(n int) int {
    digits := []byte(strconv.Itoa(n))
    mark := len(digits)
    for i := len(digits) - 1; i > 0; i-- {
        if digits[i-1] > digits[i] {
            digits[i-1]--
            mark = i
        }
    }
    for i := mark; i < len(digits); i++ {
        digits[i] = '9'
    }
    ans, _ := strconv.Atoi(string(digits))
    return ans
}

复杂度分析

时间复杂度：$O(d)$，d 是 n 的十进制位数，不超过 10。转字符数组、从右向左扫描、填 9、转回整数各是一趟线性遍历，四趟加起来仍是 $O(d)$，也可以写成 $O(\log n)$。

空间复杂度：$O(d)$，用于存放那份可修改的字符数组。原地修改数组本身不产生额外开销，只有转换出来的这一份副本与位数同阶。

关键点总结

「答案与输入共享一段前缀，然后在某一位上退一步、后面全放开」是这类「不超过 n 的最优数字」问题的通用形状。识别出这个形状，题目就从搜索变成了定位那个退让点。

扫描方向的选择是本题唯一的技术难点。修正动作会影响左侧，所以必须让扫描方向和影响传播方向一致，从右向左走一趟就能吃掉全部连锁；从左向右则要么反复迭代，要么单趟出错。

用一个 mark 变量把「后缀从哪里开始填 9」和「扫描过程」解耦，比在扫描时就动手填 9 干净得多。因为连锁修正会让这个起点不断左移，边扫边填会写进很多马上又要被覆盖的值。

mark 的初值选数组长度，是「空后缀」这个语义最自然的编码。凡是用下标表示区间起点的地方，都要单独检查「区间为空」时初值对不对。

面试视角：面试官常追问「为什么不能只修正最左边那个下降位」。答案是修正最左下降位并不足够——332 的最左下降位在下标 1，减完得到 322，下标 0 又坏了；正确的说法是要一直传播到不再产生新的下降为止，而从右向左扫描恰好一趟完成。

面试视角：主动指出「前导零由字符串转整数自动吃掉」，以及「答案位数可能比 n 少一位」，能显示你验证过 n = 10 这种小边界，而不是只跑了题面给的样例。

易错点总结

错误写法：从左向右扫描，遇到第一个下降就减一、后面填 9 并立即结束。用例 n = 332 → 在下标 1 处发现 3 > 2，减成 2 后填 9 得到 329，但 329 的前两位仍然是 3 > 2 不合法，正确答案是 299。

错误写法：减一之后不把后缀填 9。用例 n = 332 → 修正后得到 222，虽然合法但明显不是最大的，正确答案是 299。

错误写法：mark 初始化成 0。用例 n = 1234 → 全程没有触发任何修正，mark 仍是 0，填 9 的循环从头开始把整个数变成 9999，比 n 还大，正确答案是 1234。

错误写法：把「单调递增」当成严格递增。用例 n = 332 → 299 因为末尾两个 9 相等被判非法，会继续下探到 289 之类，正确答案是 299。

错误写法：填 9 的起点写成 mark + 1。用例 n = 332 → 最终 mark 是 1，只把下标 2 填成 9，得到 229，比正确答案 299 小。

错误写法：向左的循环边界写成 i >= 0。用例 n = 332 → 当 i 走到 0 时要访问 digits[-1]，直接数组越界。

错误写法：不做按位分析，从 n 开始逐个递减试探第一个合法数。用例 n = 111111110 → 答案是 99999999，中间要枚举一千一百多万个数，稳定超时。

错误写法：减的是右边那位，写成 digits[i]--。用例 n = 332 → 下标 2 从 '2' 变成 '1'，下降关系没有消除，mark 停在 2，填 9 后得到 339，比 n 还大。

相似题目

题目	难度	考察点
402. 移掉 K 位数字	中等	用单调栈维护不降前缀，删除次数是硬预算而非自由退让
670. 最大交换	中等	只允许交换一次两位，需要预处理每个后缀的最大数字及其位置
316. 去除重复字母	中等	同样追求字典序最小，但弹栈还要受「后面是否还会出现」限制