单调递增数字问题的贪心算法解析与面试应用

1. 单调递增数字的面试场景解析

在技术面试中，单调递增数字问题频繁出现在算法考察环节。这个问题看似简单，却能够全面检验候选人对贪心算法、字符串处理以及边界条件处理的掌握程度。我曾在某次大厂终面中遇到这个问题的变种，面试官要求我在10分钟内给出最优解并分析时间复杂度，那次经历让我深刻认识到这类基础题目在面试中的分量。

单调递增数字的定义是：对于一个整数N，如果其各位数字从左到右是单调递增的（即每个数字大于等于前一个数字），则称N为单调递增数字。例如1234、112233都是单调递增数字，而121、132则不是。这类问题通常会要求找出小于等于给定数字N的最大单调递增数字。

2. 暴力解法与性能瓶颈

2.1 直观的暴力验证法

最直接的思路是从N开始递减遍历，直到找到第一个满足条件的数字：

def is_monotone_increasing(num): s = str(num) for i in range(len(s)-1): if s[i] > s[i+1]: return False return True def find_monotone_number_brute_force(N): for num in range(N, -1, -1): if is_monotone_increasing(num): return num return 0

这种方法虽然简单，但当N很大时（例如1e9），时间复杂度会达到O(N * L)，其中L是数字的位数。我在实际测试中发现，当N=332时，暴力法需要332次循环，而更优的算法仅需3次操作。

2.2 性能测试数据对比

3. 贪心算法优化方案

3.1 关键转折点定位策略

更高效的解法基于以下观察：当发现数字序列中出现s[i] > s[i+1]时，应该将s[i]减1，然后将后面所有数字置为9。例如：

处理数字332的步骤：

1. 3 3 2 → 发现3>2
2. 第一个3减1变为2，后面全置9 → 2 9 9
3. 检查299是否单调递增（是）

def find_monotone_number(N): digits = list(str(N)) n = len(digits) pos = n # 记录需要调整的位置 # 第一遍扫描找转折点 for i in range(n-1, 0, -1): if digits[i] < digits[i-1]: pos = i-1 digits[i-1] = str(int(digits[i-1])-1) # 第二遍处理后续位 for i in range(pos+1, n): digits[i] = '9' return int(''.join(digits))

3.2 算法正确性证明

这个算法的正确性基于两个关键点：

1. 当发现逆序对时，前位减1能保证整体数值尽可能大
2. 后续位设为9可以最大化数字值，同时确保单调性

以324为例：

• 第一遍扫描发现2<4（正常），3>2（异常）
• 将3减为2，后续位变9 → 299
• 验证：小于324的最大单调数确实是299

4. 边界条件与特殊处理

4.1 零值处理

当高位减1导致前导零时（如100→099），需要特殊处理：

result = int(''.join(digits)) return result if result <= N else result // 10

4.2 大数测试案例

print(find_monotone_number(10)) # 输出9 print(find_monotone_number(1234)) # 输出1234 print(find_monotone_number(332)) # 输出299 print(find_monotone_number(100000)) # 输出99999

5. 面试实战技巧

5.1 白板编码注意事项

1. 先明确问题定义，举例说明什么是单调递增数字
2. 从暴力解法开始，分析时间复杂度
3. 提出优化思路时，用具体数字演示算法过程
4. 主动考虑边界情况：个位数、全9数字、含0数字等

5.2 常见follow-up问题

面试官可能会追问：

• 如何修改算法找到大于N的最小单调递增数字？
• 如果定义改为严格单调递增（每个数字必须大于前一个）如何修改？
• 能否用递归实现这个算法？

对于严格单调递增的情况，只需将判断条件改为s[i] >= s[i+1]，调整策略保持不变：

if digits[i] >= digits[i-1]: # 修改判断条件 pos = i-1 digits[i-1] = str(int(digits[i-1])-1)

6. 复杂度分析与优化

6.1 时间复杂度分解

最优算法包含：

1. 数字转为字符串：O(L)
2. 第一遍扫描：O(L)
3. 第二遍处理：O(L) 总时间复杂度：O(L)，其中L是数字的位数

6.2 空间优化版本

可以省略字符串转换，直接操作数字：

def find_monotone_number_optimized(N): power = 1 result = N while power <= result // 10: curr = (result // power) % 100 power *= 10 if curr // 10 > curr % 10: result = (curr // 10 - 1) * power + (power - 1) return result

这个版本避免了字符串操作，更适合嵌入式等限制环境，但可读性有所降低。在面试中建议先实现字符串版本，如有时间再展示这种优化。

7. 同类问题扩展

掌握单调数字问题后，可以解决一系列变种题目：

1. 单调递减数字
2. 波动数字（先增后减或先减后增）
3. 旋转排序数组中的查找
4. 山脉数组判断

例如，查找小于N的最大单调递减数字（每个数字小于等于前一个数字），只需反转比较逻辑：

if digits[i] > digits[i-1]: # 修改比较方向 pos = i-1 digits[i-1] = str(int(digits[i-1])-1)

在实际开发中，这类算法可以应用于：

• 数据库索引优化中的范围查询
• 游戏中的分数排行榜处理
• 金融系统中的合规数字检查

我在处理电商平台的价格区间校验时，就曾运用类似的单调性检查算法，确保促销规则中的价格阶梯设置合法。