面试必看：单调递增的数字

学习笔记LeetCode 738. 单调递增的数字题目描述当且仅当每个相邻位数上的数字x xx和y yy满足x ≤ y x \le yx≤y时我们称这个整数是单调递增数字。给定一个整数n nn返回小于或等于n nn的最大单调递增数字。示例输入n 10 n10n10输出9 99输入n 1234 n1234n1234输出1234 12341234输入n 332 n332n332输出299 299299数据范围0 ≤ n ≤ 10 9 0 \le n \le 10^90≤n≤1091. 算法分类贪心类本题是贪心算法在数位操作场景的经典应用依托局部最优推导全局最优的核心思想实现求解。2. 问题核心特征与算法适配性分析核心特征硬性约束目标数字每一位必须满足非递减单调递增即s [ i ] ≤ s [ i 1 ] s[i] \le s[i1]s[i]≤s[i1]优化目标在满足约束的前提下找到小于等于原数的最大值高位数值优先级远高于低位处理形式整数适合转换为字符串进行逐位修改、遍历操作大幅简化数位处理逻辑。为什么适配贪心算法策略匹配需求贪心算法优先保证高位数字尽可能大通过局部数位的修正直接推导出全局最优解完美契合本题的优化目标效率最优仅需两次线性遍历数字位数时间复杂度极低远优于暴力枚举等方案操作简洁针对违规数位执行退位修正后置位补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[i1]s[i]s[i1]则违反单调递增规则连锁反应对当前位退位后可能导致前序数位也产生违规因此选择从后向前遍历一次性处理所有连锁违规问题最优修正规则违规位退位后将其后续所有位置为9能保证修正后的数字是满足条件的最大值边界兼容字符串转整数函数会自动忽略前导零无需额外处理边界用例。6. 解题思路基于贪心策略分三步完成求解步骤1格式转换将整数n nn转换为字符串方便逐位遍历与修改操作。步骤2逆向遍历修正违规位初始化标记位flag标记后续需要置9的起始下标默认值为字符串长度。从倒数第二位开始从后向前遍历字符串若当前位数字s [ i ] s[i] s[i]后一位数字s [ i 1 ] s[i1]s[i1]将当前位退位s[i]--并更新标记位flag i1步骤3统一补9并转换结果从标记位flag开始将后续所有数位置为9最后将修正后的字符串转换为整数即为最终答案。7. 解题代码C#includestringusingnamespacestd;classSolution{public:intmonotoneIncreasingDigits(intn){// 将数字转换为字符串方便逐位操作string sto_string(n);intlens.size();// 标记位记录需要置为9的起始下标初始为字符串长度无违规则不执行置9intflaglen;// 从后向前遍历定位并修正违规数位for(intilen-2;i0;i--){if(s[i]s[i1]){// 当前位退位s[i]--;// 更新标记位后续所有位需要置9flagi1;}}// 将标记位及之后的所有数位统一置为9保证数值最大for(intiflag;ilen;i){s[i]9;}// 字符串转换为整数返回自动忽略前导零returnstoi(s);}};代码关键说明字符串处理规避了数学取位、拼接的复杂运算代码更简洁标记位flag统一记录置9起始位置避免重复遍历提升执行效率逆向遍历解决退位引发的连锁违规问题保证所有数位最终满足约束stoi函数自动处理前导零适配n 0 n0n0等边界场景。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的策略高效求解目标值核心技巧是将整数转为字符串处理数位搭配逆向遍历解决连锁违规问题该方案是数位约束类贪心题目的通用模板可直接迁移至同类场景。