LeetCode 738. 单调递增的数字

◎

本节目标

从右向左发现递减冲突后回退高位，并将后缀置为 9 构造最大合法数字。

这是贪心综合中数字回退构造的拓展题。

题意与约束

给定非负整数 n，求不大于 n 的最大整数，使其从左到右各位非递减。

直接思路与瓶颈

从 n 开始向下枚举直到合法，数值间隔可能很大。只修改第一个冲突位也不够：减一后还可能与更高位形成新冲突。

贪心模型与算法推导

把数字转为字符数组，从右向左扫描。若 digits[i] < digits[i-1]，将 i-1 减一并记录从 i 开始的后缀；扫描结束后，后缀全部置为 9。

正确性依据

首次冲突说明当前前缀不能原样保留；把冲突左侧最低可改变的高位减一，才有机会让整体不超过 n。高位已变小后，为最大化数值，所有更低位应尽量取 9。右向左扫描确保连锁借位后的新冲突也会被处理。

样例执行过程

332 从右看 2<3，得到 322 并标记后缀；继续发现中间 2<3，得到 222，最终把后两位设为 9，答案为 299。

代码实现

C++

C++17

#include <string>
using namespace std;

class Solution {
public:
    int monotoneIncreasingDigits(int n) {
        string digits = to_string(n);
        int marker = static_cast<int>(digits.size());
        for (int i = static_cast<int>(digits.size()) - 1; i > 0; i--) {
            if (digits[i] < digits[i - 1]) {
                digits[i - 1]--;
                marker = i;
            }
        }
        for (int i = marker; i < static_cast<int>(digits.size()); i++) digits[i] = '9';
        return stoi(digits);
    }
};

Python

Python 3

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        digits = list(str(n))
        marker = len(digits)
        for index in range(len(digits) - 1, 0, -1):
            if digits[index] < digits[index - 1]:
                digits[index - 1] = str(int(digits[index - 1]) - 1)
                marker = index
        for index in range(marker, len(digits)):
            digits[index] = '9'
        return int(''.join(digits))

复杂度分析

数字位数为 d，时间 O(d)，字符数组空间 O(d)。

边界与易错点

• 必须从右向左扫描，处理连续回退。
• 已经单调递增的数字无需修改。
• 如 10，回退后前导零在转回整数时自然消失。

模式迁移

受上界限制的最大数字构造，常在最右侧冲突处回退更高位，再用允许的最大值填满后缀。