738. 单调递增的数字（Monotone Increasing Digits）
频次 ★★★ · 难度 🟡 · 高频：字节
题目
给定一个非负整数 n，返回小于或等于 n 的最大数字，且该数字的各位数字单调递增（相邻位非递减，即高位 ≤ 低位）。
示例：
输入: n = 10
输出: 9
输入: n = 1234
输出: 1234
输入: n = 332
输出: 299
思路
贪心（从右向左扫描）：将数字转为字符数组，从右向左遍历。当发现 chars[i-1] > chars[i]（即高位 > 低位，违反单调递增），执行：
chars[i-1]--（高位减 1）- 标记位置 i，之后从 i 到末尾全部变成 ‘9’
贪心原理：遇到第一个递减位置时，把高位减 1 后低位全变 9，得到的数字最大且满足单调递增。
代码
public int monotoneIncreasingDigits(int n) {
char[] chars = String.valueOf(n).toCharArray();
int flag = chars.length; // 标记从哪开始全部变 9
for (int i = chars.length - 1; i > 0; i--) {
if (chars[i - 1] > chars[i]) { // 高位 > 低位，违反单调递增
chars[i - 1]--; // 高位减 1
flag = i; // 从 i 开始全部变 9
}
}
for (int i = flag; i < chars.length; i++) {
chars[i] = '9';
}
return Integer.parseInt(new String(chars));
}复杂度
- 时间：O(L) —— L 为数字位数，最多 10 位（int 范围）
- 空间：O(L) —— 字符数组
边界条件
- n = 0：返回 0
- n 已是单调递增：返回 n 本身
- n 全为相同数字（如 111）：返回 n
- 多段递减（如 332）：
flag只会记录最后一次递减位置，因为高位减 1 后可能引发新的递减，需要继续向左检查
变式
- 402. 移掉 K 位数字：移除 k 位数字使剩余最小，同为贪心 + 单调栈思路
- 670. 最大交换：最多交换一次使数字最大，贪心
易错点
- flag 初始化为 chars.length：如果 n 本身就是单调递增，flag 不会更新，循环全变 9 不会执行，直接返回原值
- 从右向左遍历：从左向右遍历无法正确处理”高位减 1 后前面可能继续递减”的情况。例如 332，从左向右只看到 3>3(不成立)、3>2(成立)，把 3 减成 2 得 229，但 22 仍递减需要再处理。从右向左一遍就够
- flag 记录的是”开始变 9 的位置”：不是记录递减位置，而是递减位置 + 1（即高位减 1 后，其后所有位变 9）
面试追问
- 为什么从右向左遍历？ 从右向左时，高位减 1 后可能引发新的递减关系，但 i 指针继续向左移动，下一轮循环会自然检查到。如果从左向右，需要回退重扫
- 为什么遇到递减后低位全变 9？ 贪心：在高位减 1 的前提下，低位全变 9 能得到最大的满足单调递增的数字
关联题
- 同套路：402. 移掉 K 位数字 —— 贪心 + 单调栈
- 进阶：670. 最大交换 —— 交换变体
- 知识点：数字位贪心模板见贪心