LeetCode 题解工作台
单调递增的数字
当且仅当每个相邻位数上的数字 x 和 y 满足 x 时，我们称这个整数是 单调递增 的。 给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。 示例 1: 输入: n = 10 输出: 9 示例 2: 输入: n = 1234 输出: 1234 示例 3: 输入: n = 3…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
从数字 `n` 的高位开始，找到第一个不满足 $n_{i-1} \le n_i$ 的位置 。 然后，从后往前，只要发现 $n_{i-1} \gt n_i$，就将 减 1。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例 1:
输入: n = 10 输出: 9
示例 2:
输入: n = 1234 输出: 1234
示例 3:
输入: n = 332 输出: 299
提示:
0 <= n <= 109
解题思路
方法一：贪心
从数字 n 的高位开始，找到第一个不满足 的位置 。
然后，从后往前，只要发现 ，就将 减 1。
最后将位置 之后的所有数字都置为 9 即可。
时间复杂度 ，空间复杂度 。
class Solution:
def monotoneIncreasingDigits(self, n: int) -> int:
s = list(str(n))
i = 1
while i < len(s) and s[i - 1] <= s[i]:
i += 1
if i < len(s):
while i and s[i - 1] > s[i]:
s[i - 1] = str(int(s[i - 1]) - 1)
i -= 1
i += 1
while i < len(s):
s[i] = '9'
i += 1
return int(''.join(s))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(log n) because each digit is processed once, and space complexity is O(log n) to store the digits in an array representation of n. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Asks about handling digit violations and the greedy invariant.
- question_mark
Checks if you understand why setting trailing digits to 9 maximizes the number.
- question_mark
Looks for a clear explanation of digit-by-digit adjustments without overshooting n.
常见陷阱
外企场景- error
Forgetting to set all digits after a decrement to 9, breaking maximality.
- error
Misidentifying which digit to decrement when multiple violations exist.
- error
Attempting a brute-force scan of all numbers ≤ n instead of a greedy digit approach.
进阶变体
外企场景- arrow_right_alt
Find the smallest monotone decreasing number ≥ n.
- arrow_right_alt
Compute the count of monotone increasing numbers ≤ n.
- arrow_right_alt
Modify the approach to work with a custom base instead of decimal digits.