LeetCode 738. 单调递增的数字
题目描述
题意分析
求不超过
n、各位从左到右不下降的最大整数。相邻位可以相等，这里的“单调递增”指非严格递增。数字大小首先由高位决定，所以应尽量保留原数的高位，只在无法保持合法时降低某一位。
解法：从右向左修正
核心思路
[!blue]
发现
digits[i - 1] > digits[i]时，若保持前面的高位不变，就不能直接增大右位来消除下降，否则可能超过原数。应让左位减 1；一旦某个高位变小，右侧就可以尽量取大，因此最终把它后面的所有位填成 9。但左位减 1 后，可能又比它左边的数字小，产生新的下降。于是从右向左扫描，让这次修正继续向左传播；直到前缀重新满足不下降，或已经到达最高位。每次修正只减 1，保留了该位置在必须降低时能够取到的最大值。
用
mark记录最终需要填 9 的后缀起点。发生下降时降低digits[i - 1]，并令mark = i；如果后续修正传播到更左侧，mark也随之左移。扫描期间暂不填 9，以便下一轮仍能看见刚减小的数位，判断是否还要向左修正。全部检查完后，再统一把mark及其右侧改为 9。最终保留下来的前缀没有下降，后缀全部为 9，与前缀也能衔接。若发生修改，结果与原数最早不同的那一位恰好减 1，因此结果一定小于原数；更高位保持不动，降低的这一位取最大可行值，后缀也取最大值，得到的就是最大合法结果。若没有下降，
mark保持为长度，直接返回原数。
解题步骤
- 将
n转为可修改的十进制位数组，令mark等于数组长度，表示暂时没有需要填 9 的后缀。- 从最右侧相邻数位向左检查。若左位大于右位，将左位减 1，并将
mark更新为右位下标。- 扫描结束后，把下标从
mark到末尾的数位全部设为 9。- 将数位数组转回整数，转换会自然去掉可能出现的前导 0。
n = 0或仅有一位时，无需进行任何修正。
代码实现
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));
}
}
import "strconv"
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的十进制位数。转换、反向扫描和填充后缀都只需线性时间。- 空间复杂度：$O(d)$，保存可修改的数位数组和转换时的字符串。
关键点总结
[!green]
- 修正向左传播，填九延迟到扫描完成。
mark=长度表示没有待填后缀。
易错点总结
[!yellow]
- 只处理第一次发现的下降就结束，会漏掉减 1 后向更高位产生的连锁下降。
- 不填九虽可能合法，却不是最大答案。
- 把相等位也当成下降，会排除合法的重复数字。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 402. 移掉 K 位数字 | 中等 | 同样在数位首次不满足字典序目标时调整前缀，本题降低数位并填充后缀，原题删除固定数量字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！