贪心算法专题(十五)：借位与填充的智慧——「单调递增的数字」
哈喽各位，我是前端L。
欢迎来到贪心算法专题第十五篇！ 这道题非常有意思，有点像小学数学里的“借位减法”。 题目要求：给定一个非负整数N，找出小于或等于N的最大整数，且该整数的每一位数字必须是单调递增的（即1234可以，132不行）。
力扣 738. 单调递增的数字
https://leetcode.cn/problems/monotone-increasing-digits
题目分析：
输入：
n = 332输出：
299332不行，因为3 > 2（最后两位破坏了递增）。比它小的最大递增数是
299。
例子 2：n = 1234
输出：
1234（本身就是递增的，不用变）。
例子 3：n = 10
输出：
9。
核心思维：一旦违规，前位减一，后位全变九
贪心策略来源于生活中的直觉： 这就好比你要把332变成递增。
我们发现百位
3和十位3没问题。但是十位
3和个位2出问题了：3 > 2。为了消除这个“逆序”，我们必须把十位的
3变小一点，变成2。既然十位变小了（高位变小了），为了让整体数值尽可能大（题目要求最大整数），个位（以及后面所有位）就可以放飞自我，全部变成最大的数字9。
结果：
329。
等等，还没完！变成329后，我们发现百位3和十位2又构成了逆序（3 > 2）。 6. 继续借位：把百位3减一变成2。 7. 后面的十位变成9。 8. 结果：299。完美！
遍历顺序：从后往前为什么要从后往前遍历？ 因为修改高位会影响低位。正如刚才的例子，332->329->299。如果从前往后遍历，你处理完百位和十位，再处理十位和个位时，可能会导致前面的关系失效，需要回头重做。 从后往前遍历，可以利用前面处理好的“9”的特性，一次扫描搞定。
算法流程 (JavaScript)
类型转换：数字不好操作每一位，先转成字符串数组
strNum。标记位
flag：记录从哪一位开始，后面的数字都要变成 9。初始化为strNum.length（默认不需要变）。倒序遍历：从
i = strNum.length - 1遍历到1。比较
strNum[i-1](前一位) 和strNum[i](当前位)。如果
strNum[i-1] > strNum[i]（出现逆序，前一位太大了）：前一位减 1：
strNum[i-1]--。记录标记：
flag = i。这意味着从i开始往后的都要变 9。
填充 9：从
flag到末尾，全部赋值为'9'。输出：转回数字
parseInt。
代码实现
深度模拟
n = 100
数组
[1, 0, 0]，flag = 3。i = 2: 比较0和0。相等，没事。i = 1: 比较1和0。1 > 0，出事了！strNum[0]减 1 变成0。数组现为[0, 0, 0]。flag更新为1。
循环结束。
填充 9：从
flag=1开始。strNum[1] = 9strNum[2] = 9数组变
[0, 9, 9]。
返回
99。正确。
总结
这道题虽然代码简单，但包含了贪心算法中**“局部调整影响全局”**的思想。
局部最优：遇到逆序就借位，保证当前位不违规。
全局最优：借位后把后面全变 9，保证数值最大。
下一题预告：监控二叉树
准备好了吗？我们要迎来贪心算法的最终大 Boss——LC 968. 监控二叉树(Hard)。 这是一道树形 DP 和贪心结合的题目，难度远超刚才的糖果和气球。
题目：给定一棵二叉树，我们在节点上安装摄像头。每个摄像头能监控自己、父节点、子节点。
目标：用最少的摄像头监控整棵树。
这道题的贪心策略非常反直觉：永远不要把摄像头放在叶子节点上！为什么？因为叶子节点放摄像头太浪费了（它没有子节点可以监控）。
这将是我们贪心专题的毕业考试，攻克它，我们就进军单调栈！ 下期见！