贪心算法专题(十五)：借位与填充的智慧——「单调递增的数字」

哈喽各位，我是前端L。

欢迎来到贪心算法专题第十五篇！ 这道题非常有意思，有点像小学数学里的“借位减法”。 题目要求：给定一个非负整数N，找出小于或等于N的最大整数，且该整数的每一位数字必须是单调递增的（即1234可以，132不行）。

力扣 738. 单调递增的数字

https://leetcode.cn/problems/monotone-increasing-digits

题目分析：

• 输入：n = 332

• 输出：299

  • 332不行，因为3 > 2（最后两位破坏了递增）。

  • 比它小的最大递增数是299。

例子 2：n = 1234

• 输出：1234（本身就是递增的，不用变）。

例子 3：n = 10

• 输出：9。

核心思维：一旦违规，前位减一，后位全变九

贪心策略来源于生活中的直觉： 这就好比你要把332变成递增。

1. 我们发现百位3和十位3没问题。

2. 但是十位3和个位2出问题了：3 > 2。

3. 为了消除这个“逆序”，我们必须把十位的3变小一点，变成2。

4. 既然十位变小了（高位变小了），为了让整体数值尽可能大（题目要求最大整数），个位（以及后面所有位）就可以放飞自我，全部变成最大的数字9。

5. 结果：329。

等等，还没完！变成329后，我们发现百位3和十位2又构成了逆序（3 > 2）。 6. 继续借位：把百位3减一变成2。 7. 后面的十位变成9。 8. 结果：299。完美！

遍历顺序：从后往前为什么要从后往前遍历？ 因为修改高位会影响低位。正如刚才的例子，332->329->299。如果从前往后遍历，你处理完百位和十位，再处理十位和个位时，可能会导致前面的关系失效，需要回头重做。 从后往前遍历，可以利用前面处理好的“9”的特性，一次扫描搞定。

算法流程 (JavaScript)

1. 类型转换：数字不好操作每一位，先转成字符串数组strNum。

2. 标记位flag：记录从哪一位开始，后面的数字都要变成 9。初始化为strNum.length（默认不需要变）。

3. 倒序遍历：从i = strNum.length - 1遍历到1。

   • 比较strNum[i-1](前一位) 和strNum[i](当前位)。

   • 如果strNum[i-1] > strNum[i]（出现逆序，前一位太大了）：

     • 前一位减 1：strNum[i-1]--。

     • 记录标记：flag = i。这意味着从i开始往后的都要变 9。

4. 填充 9：从flag到末尾，全部赋值为'9'。

5. 输出：转回数字parseInt。

代码实现

深度模拟

n = 100

1. 数组[1, 0, 0]，flag = 3。

2. i = 2: 比较0和0。相等，没事。

3. i = 1: 比较1和0。1 > 0，出事了！

   • strNum[0]减 1 变成0。数组现为[0, 0, 0]。

   • flag更新为1。

4. 循环结束。

5. 填充 9：从flag=1开始。

   • strNum[1] = 9

   • strNum[2] = 9

   • 数组变[0, 9, 9]。

6. 返回99。正确。

总结

这道题虽然代码简单，但包含了贪心算法中**“局部调整影响全局”**的思想。

• 局部最优：遇到逆序就借位，保证当前位不违规。

• 全局最优：借位后把后面全变 9，保证数值最大。

---

下一题预告：监控二叉树

准备好了吗？我们要迎来贪心算法的最终大 Boss——LC 968. 监控二叉树(Hard)。 这是一道树形 DP 和贪心结合的题目，难度远超刚才的糖果和气球。

• 题目：给定一棵二叉树，我们在节点上安装摄像头。每个摄像头能监控自己、父节点、子节点。

• 目标：用最少的摄像头监控整棵树。

这道题的贪心策略非常反直觉：永远不要把摄像头放在叶子节点上！为什么？因为叶子节点放摄像头太浪费了（它没有子节点可以监控）。

这将是我们贪心专题的毕业考试，攻克它，我们就进军单调栈！ 下期见！