leetcode每日一题：738. 单调递增的数字
leetcode每日一题：738. 单调递增的数字
leetcode每日一题：738. 单调递增的数字：https://leetcode-cn.com/problems/monotone-increasing-digits/
一起刷题吧
一、题意分析
输入：非负整数（大于等于0） 输出：比输入小或等的，且对于这个数值，从左到右，呈单调递增（包括等） 难度：中等 标签：贪心
示例 1: 输入: N = 10 输出: 9
示例 2: 输入: N = 1234 输出: 1234
示例 3: 输入: N = 332 输出: 299
二、参考代码
这个题目，个人认为是一个数学题目，可以通过数学思维来解决。要想数值最大且满足题目要求，则需要在高位尽可能不变，低位最大的情况下去做转变，低位最大显然就是变成 9，而此时相应的高位需要减小。这里以几个特殊数值为例说明这个过程：
示例一：N = 332
- 个位数：2，符合题目要求，继续向前遍历，N = 33
- 个位数：3，3 > 2，不符合题目要求，这个时候需要做变化。秉承低位最大的原则，原来的 2 应该变为 9，高位尽可能不变，但此时需要变化，那想要最大，则应该变为比它小的最大的一个数值，当前高数是 3，比它小的最大一个数值显然是 2，因此此时值为 29， N = 3
- 个位数为3，此时不符合题目要求，按同样的标准做替换，值为 299 此时 N = 0，结束循环，因此最终结果为 299
示例二：N = 4332
- 个位数：2，符合要求，N = 433
- 个位娄：3，不符合要求，转换结果为 29，N = 43
- 个位数：3，不符合要求，转换结果为 299，N = 4
- 个位数：4，不符合要求，转换结果为 3999, N = 0
示例三：N = 45443
- 个位数：3，符合要求，N = 4544
- 个位数：4，不符合要求，转换结果为 39， N = 454
- 个位数：4，不符合要求，转换结果为 399，N = 45
- 个位数：5，不符合要求，转换结果为 4999，N = 4
- 个位数：4，符合要求，结果为 44999，N = 0
同样的推理，大家可以试下：N = 4332 以及 N = 4321 这两组数据。通过观察，我们可以发现如果新的个位数与它前一位比较，如果符合题目中的递增要求，则直接写入在最前位即可，如果不符合，则需要做转换，转换的规律也很简单，即将原来记录的结果每一位都转换为 9，即低位最大，而当前获取的个位数减 1 之后，写入在记录的最前位即可。
通过上面的推导过程，我们知道需要记录前一位被比较的数值，同时还涉及到低位替换为 9 的过程，我们可以在遍历的过程把低位替换 9 的结果保存下来，在需要替换时直接取值即可，参考代码如下：
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
if N <= 0:
return N
# 前一个被比较值
p = N % 10
# 最后返回的结果值
result = p
# 相当于记录位数
mul = 10
# 记录将每一位替换为 9 之后的结果，方便替换时直接取值
nine = 9
# N 值向后移
N = N // 10
while N:
r = N % 10
if r > p:
# 当前位变成p，已经经过的位都变成9
result = nine + mul * (r - 1)
p = r - 1
else:
result = result + mul * r
p = r
N = N // 10
nine = nine + 9 * mul
mul = mul * 10
return result
执行情况：
执行用时：44 ms, 在所有 Python3 提交中击败了 40.91% 的用户
内存消耗：14.7 MB, 在所有 Python3 提交中击败了 5.70% 的用户
能过，但执行速度上并不是最优的。这里我们重新审视一下整个过程，可以发现这个从后往前遍历里有很多重复的转换过程，高位做了转换相当于低位做了转换，那我们是否可以从前往后遍历呢？显然也是可以的。
从前往后遍历的思路也很简单，遍历找到第一个不满足递增条件的位置，将此位置减 1，此位置之后的数值全变成 9 即可。但需要注意的是，因为涉及到有一个位置会减 1，所以可能出现减 1 之后，与前一位不再是递增关系了，因此当我们找到了第一个不满足递增条件的位置后，要从当前位置往前找，找到第一个满足减 1 之后仍然满足递增条件位置。也就是说两个寻找：
- 从前往后找到第一个不满足递增条件的位置
- 从后往前找到第一个满足减 1 后仍然满足递增条件的位置
- 找到位置之后的元素变成 9，当前位置减 1，就是最终结果
实现参考代码如下：
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
if N <= 0:
return N
N = list(str(N))
i = 1
# 记录最后一个满足减一之后仍然符合递增条件的位置
pos = 0
while i < len(N) and N[i] >= N[i - 1]:
if N[i] > N[i - 1]:
pos = i
i += 1
if i < len(N):
inv = int(N[i])
if inv - 1 < int(N[i - 1]):
i = pos
N[i] = str(int(N[i]) - 1)
for j in range(i + 1, len(N)):
N[j] = '9'
return int("".join(N))
这次提交后时间上击败了 88% 的用户，看了下提交里超过 100% 的用户代码，提交了下，运行和上面代码是一样的。不过那个代码的思路也比较有意思，这里贴上代码（因为从提交中找到的，没有来源可标注）：
class Solution_others:
def monotoneIncreasingDigits(self, N: int) -> int:
digits = []
if N == 0:
return 0
while N:
digits.append(N % 10)
N //= 10
digits = digits[::-1]
marker = len(digits) # marker是第一个需要改成9的数字
for i in range(len(digits) - 1, 0, -1): # 从低位到高位遍历
if digits[i - 1] > digits[i]:
digits[i - 1] -= 1 # 只减1，给前面的数留下更多空间，后面的数都会改成9的
marker = i
for i in range(marker, len(digits)):
digits[i] = 9
res = 0
for i in range(len(digits)):
res = res * 10 + digits[i]
return res