社区首页 >专栏 >leetcode每日一题：738. 单调递增的数字

leetcode每日一题：738. 单调递增的数字

用户7685359

发布于 2020-12-22 07:36:52

73500

代码可运行

文章被收录于专栏：FluentStudyFluentStudy

运行总次数：0

代码可运行

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