学习笔记：LeetCode 738. 单调递增的数字
题目描述
当且仅当每个相邻位数上的数字x xx和y yy满足x ≤ y x \le yx≤y时，我们称这个整数是单调递增数字。
给定一个整数n nn，返回小于或等于n nn的最大单调递增数字。
示例
- 输入：n = 10 n=10n=10，输出：9 99
- 输入：n = 1234 n=1234n=1234，输出：1234 12341234
- 输入：n = 332 n=332n=332，输出：299 299299
数据范围
0 ≤ n ≤ 10 9 0 \le n \le 10^90≤n≤109
1. 算法分类
贪心类
本题是贪心算法在数位操作场景的经典应用，依托局部最优推导全局最优的核心思想实现求解。
2. 问题核心特征与算法适配性分析
核心特征
- 硬性约束：目标数字每一位必须满足非递减（单调递增），即s [ i ] ≤ s [ i + 1 ] s[i] \le s[i+1]s[i]≤s[i+1]；
- 优化目标：在满足约束的前提下，找到小于等于原数的最大值，高位数值优先级远高于低位；
- 处理形式：整数适合转换为字符串进行逐位修改、遍历操作，大幅简化数位处理逻辑。
为什么适配贪心算法
- 策略匹配需求：贪心算法优先保证高位数字尽可能大，通过局部数位的修正，直接推导出全局最优解，完美契合本题的优化目标；
- 效率最优：仅需两次线性遍历数字位数，时间复杂度极低，远优于暴力枚举等方案；
- 操作简洁：针对违规数位执行退位修正+后置位补9，逻辑直观易实现，无复杂计算。
备选方案对比
| 解法 | 时间复杂度 | 空间复杂度 | 弃选原因 |
|---|---|---|---|
| 暴力枚举 | O ( n ⋅ l e n ) O(n \cdot len)O(n⋅len) | O ( 1 ) O(1)O(1) | n nn最大为10 9 10^9109，会直接超时，无法通过测试 |
| 动态规划 | O ( l e n ⋅ 10 ) O(len \cdot 10)O(len⋅10) | O ( l e n ⋅ 10 ) O(len \cdot 10)O(len⋅10) | 状态定义繁琐，实现复杂，相比贪心无效率与编码优势 |
3. 问题关键词
单调递增数字、非递减数位、最大取值、贪心算法、数位处理、退位补9、字符串转换
4. 解题模式识别
题型定位
本题属于数位约束类贪心问题，具备标准化解题特征：
- 对整数的每一位数字定义明确约束条件；
- 求解满足约束条件的极值数字（最大值/最小值）；
- 通用解题模板：数字转字符串→ \to→定位违规数位→ \to→贪心策略修正→ \to→字符串转回数字。
拓展场景
该解题模板可迁移至同类数位优化问题，如：拼接数字得到最大/最小值、带约束的数位构造问题等。
5. 问题分析
- 违规判定：从前向后遍历，若出现s [ i ] > s [ i + 1 ] s[i] > s[i+1]s[i]>s[i+1]，则违反单调递增规则；
- 连锁反应：对当前位退位后，可能导致前序数位也产生违规，因此选择从后向前遍历，一次性处理所有连锁违规问题；
- 最优修正规则：违规位退位后，将其后续所有位置为9，能保证修正后的数字是满足条件的最大值；
- 边界兼容：字符串转整数函数会自动忽略前导零，无需额外处理边界用例。
6. 解题思路
基于贪心策略，分三步完成求解：
步骤1：格式转换
将整数n nn转换为字符串，方便逐位遍历与修改操作。
步骤2：逆向遍历修正违规位
初始化标记位flag（标记后续需要置9的起始下标），默认值为字符串长度。
从倒数第二位开始从后向前遍历字符串：
- 若当前位数字s [ i ] > s[i] >s[i]>后一位数字s [ i + 1 ] s[i+1]s[i+1]，将当前位退位
s[i]--，并更新标记位flag = i+1；
步骤3：统一补9并转换结果
从标记位flag开始，将后续所有数位置为9，最后将修正后的字符串转换为整数，即为最终答案。
7. 解题代码（C++）
#include<string>usingnamespacestd;classSolution{public:intmonotoneIncreasingDigits(intn){// 将数字转换为字符串，方便逐位操作string s=to_string(n);intlen=s.size();// 标记位：记录需要置为9的起始下标，初始为字符串长度（无违规则不执行置9）intflag=len;// 从后向前遍历，定位并修正违规数位for(inti=len-2;i>=0;i--){if(s[i]>s[i+1]){// 当前位退位s[i]--;// 更新标记位，后续所有位需要置9flag=i+1;}}// 将标记位及之后的所有数位统一置为9，保证数值最大for(inti=flag;i<len;i++){s[i]='9';}// 字符串转换为整数返回，自动忽略前导零returnstoi(s);}};代码关键说明
- 字符串处理：规避了数学取位、拼接的复杂运算，代码更简洁；
- 标记位
flag：统一记录置9起始位置，避免重复遍历，提升执行效率； - 逆向遍历：解决退位引发的连锁违规问题，保证所有数位最终满足约束；
stoi函数：自动处理前导零，适配n = 0 n=0n=0等边界场景。
8. 复杂度分析
时间复杂度
O ( l e n ) O(len)O(len)，l e n lenlen为数字n nn的位数（最多10位）。
算法包含两次线性遍历，整体为常数级别的线性时间复杂度，执行效率极高。
空间复杂度
O ( l e n ) O(len)O(len)，用于存储数字对应的字符串，属于必要的辅助空间。
关键注意事项
- 遍历方向：必须采用从后向前遍历，才能处理退位带来的前序数位连锁违规问题；
- 独立置9：统一将标记位后所有位置9，是保证结果为最大值的核心操作；
- 结果转换：利用库函数自动处理前导零，简化边界场景的代码逻辑。
总结
- 本题最优解法为贪心算法，通过退位修正+后置位统一补9的策略，高效求解目标值；
- 核心技巧是将整数转为字符串处理数位，搭配逆向遍历解决连锁违规问题；
- 该方案是数位约束类贪心题目的通用模板，可直接迁移至同类场景。
