单调递增的数字如何用贪心求不超过 N 的最大值？（LeetCode 738）

简化版

从右往左找第一个破坏单调递增的位置：如果 digits[i-1] > digits[i]，就把 digits[i-1]--，并把它后面的所有位标记为 9。

这样能保证结果不超过 N，同时后缀尽量大，所以是最大合法数。

详细版

题目要求找 <= N 的最大整数，使数字从高位到低位单调不下降。把 N 转成字符数组，从右往左扫描，一旦发现左位大于右位，就说明这个前缀无法保持原值，需要把左位减 1，并把后面都改成 9。

从右往左很重要，因为左位减 1 后，可能又破坏它和更左一位的关系。例如 332：先处理 3>2 得到 329，此时前面的 3>2 仍违规，需要继续得到 299。

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

完整版教学

一、题目里的单调递增是什么意思

这里的「单调递增」按 LeetCode 原意是每一位数字从左到右不下降，即 x1 <= x2 <= x3 ...。例如 1234、1129、999 都合法，332、120、987 不合法。我们要在所有不超过 N 的合法数里找最大的。

如果从数值大小看，高位越大越重要。因此理想情况是尽量保留 N 的高位不变；只有在某处破坏单调时，才不得不降低某个高位，然后把后缀调到最大。

二、为什么违规时要降低左边一位

当出现 digits[i-1] > digits[i]，例如 32，这两个相邻位已经违反不下降。要让结果不超过原数，不能把右边 2 提高到 3，因为这可能让整体超过 N 的对应前缀；安全做法是把左边 3 降成 2，使前缀变小。

一旦前缀变小，后面的位就可以尽量取最大，也就是全部变成 9。这正是「不超过 N」和「尽量大」之间的平衡：前面降一点保证合法上界，后面全 9 追回最大值。

三、为什么要从右往左扫描

左位减 1 可能影响它和更左一位的关系。如果从左往右，修改后还要回头，逻辑容易漏。右往左扫描可以把这种影响自然传递到更左侧。

以 N = 332 为例：

原始: 3 3 2
右侧违规: 第二个 3 > 2，第二个 3 减 1，后缀标记为 9 -> 3 2 9
继续左看: 第一个 3 > 2，第一个 3 减 1，后缀标记提前 -> 2 9 9
答案: 299

如果只处理最右边一次，会得到 329，仍然不是单调递增。

四、mark 的作用

mark 记录从哪一位开始要全部改成 9。每次发现违规并把 a[i-1]-- 后，i 及其右侧都可以在最终结果中变成 9。因为更左前缀已经变小，后缀取最大不会超过原数。

N = 120
1 2 0
发现 2 > 0: 2 减为 1，mark=2
数组暂为 1 1 0
mark 后全 9: 1 1 9

得到 119，它不超过 120，且是最大的单调递增数字。

五、对比几种常见数字

N	处理过程	答案
`1234`	没有违规	`1234`
`10`	`1>0`，降 1 后补 9	`9`
`120`	`2>0`，降 2 后补 9	`119`
`332`	连续向左传递	`299`

这些例子覆盖了无需修改、最高位变 0、普通后缀补 9、连续回退四类情况。

六、为什么后缀一定全部变 9

当前缀已经比原数小，后缀再怎么取 9 都不会超过 N。为了让结果最大，后缀自然应该取每一位的最大数字 9。同时，因为后缀位于被降低后的数字右侧，只要左侧降低点不大于第一位 9，单调性也不会被破坏。

记忆钩子：前缀一旦降了，后缀就自由了；自由后要最大，所以全填 9。

七、常见误区与追问

误区：从左往右找到第一次违规就结束。 降低某位后可能继续影响左侧，需要右往左传递。
误区：把右边较小位升高。 这可能让数字超过 N，不满足题目要求。
误区：违规后只把当前位改掉，不补 9。 后缀不补 9 会错过更大的合法答案。
追问：10 为什么返回 9？ 1 降成 0 后后缀补 9，解析整数时前导 0 消失，得到 9。
追问：复杂度是多少？ 数字位数为 d，时间 O(d)，字符数组空间 O(d)。
追问：为什么后缀全 9 仍保持单调？ 降低后的左位最大为 8 或更小，右侧 9 不会小于它。

八、加强记忆

单调递增数字的核心是「右往左找逆序，左位减一，右边全九」。逆序说明原前缀不能保留，必须降低左边一位来保证不超过 N；降低之后，右侧后缀已经没有上界压力，全部填 9 才最大。右往左扫描可以处理 332 -> 299 这种连锁回退。记住「降左位保合法，补九保最大」，这题就很稳。

简化版

详细版